Mathematics – Logic
Scientific paper
2009-10-28
The Journal of Symbolic Logic 76 (2011), 575-602
Mathematics
Logic
26 pages, 3 figures, to appear in Journal of Symbolic Logic
Scientific paper
10.2178/jsl/1305810765
We study the computability-theoretic complexity and proof-theoretic strength of the following statements: (1) "If X is a well-ordering, then so is epsilon_X", and (2) "If X is a well-ordering, then so is phi(alpha,X)", where alpha is a fixed computable ordinal and phi the two-placed Veblen function. For the former statement, we show that omega iterations of the Turing jump are necessary in the proof and that the statement is equivalent to ACA_0^+ over RCA_0. To prove the latter statement we need to use omega^alpha iterations of the Turing jump, and we show that the statement is equivalent to Pi^0_{omega^alpha}-CA_0. Our proofs are purely computability-theoretic. We also give a new proof of a result of Friedman: the statement "if X is a well-ordering, then so is phi(X,0)" is equivalent to ATR_0 over RCA_0.
Marcone Alberto
Montalbán Antonio
No associations
LandOfFree
The Veblen functions for computability theorists does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Veblen functions for computability theorists, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Veblen functions for computability theorists will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-718534