From hierarchies to well-foundedness

Flumini, Dandolo; Sato, Kentaro (2014). From hierarchies to well-foundedness. Archive for mathematical logic, 53(7-8), pp. 855-863. Springer International 10.1007/s00153-014-0392-9

[img] Text
art%3A10.1007%2Fs00153-014-0392-9.pdf - Published Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (177kB) | Request a copy
[img]
Preview
Text
fs14.pdf - Accepted Version
Available under License Publisher holds Copyright.

Download (273kB) | Preview

We highlight that the connection of well-foundedness and recursive definitions is more than just convenience. While the consequences of making well-foundedness a sufficient condition for the existence of hierarchies (of various complexity) have been extensively studied, we point out that (if parameters are allowed) well-foundedness is a necessary condition for the existence of hierarchies e.g. that even in an intuitionistic setting (Π01−CA0)α⊢wf(α)where(Π01−CA0)α stands for the iteration of Π01 comprehension (with parameters) along some ordinal α and wf(α) stands for the well-foundedness of α.

Item Type: Journal Article (Original Article)
Division/Institute: 08 Faculty of Science > Institute of Computer Science (INF) > Logic and Theory Group (LTG)
08 Faculty of Science > Institute of Computer Science (INF)
UniBE Contributor: Flumini, Dandolo and Sato, Kentaro
Subjects: 000 Computer science, knowledge & systems
500 Science > 510 Mathematics
ISSN: 0933-5846
Publisher: Springer International
Language: English
Submitter: Florian Ranzi
Date Deposited: 23 Jan 2015 14:50
Last Modified: 21 Sep 2015 09:47
Publisher DOI: 10.1007/s00153-014-0392-9
BORIS DOI: 10.7892/boris.61787
URI: http://boris.unibe.ch/id/eprint/61787

Actions (login required)

Edit item Edit item
Provide Feedback