The Veblen functions for computability theorists
From MaRDI portal
ACAarithmetical comprehensioncomputabilitycomputable linear orderingcomputable ordinaljumpomega jumpordinal analysisreverse mathematics
Foundations of classical theories (including reverse mathematics) (03B30) Theory of numerations, effectively presented structures (03D45) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Recursive ordinals and ordinal notations (03F15) Second- and higher-order arithmetic and fragments (03F35)
Abstract: 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.
Recommendations
- Computability theory of generalized functions
- scientific article; zbMATH DE number 4112573
- Computability and the Implicit Function Theorem
- scientific article; zbMATH DE number 1746042
- A computability theoretic equivalent to Vaught's conjecture
- On total functions, existence theorems and computational complexity
- A new characterization of computable functions
- On classes of computable functions
- Publication:4207514
- Computability over the partial continuous functionals
Cites work
- scientific article; zbMATH DE number 5604770 (Why is no real title available?)
- scientific article; zbMATH DE number 4033738 (Why is no real title available?)
- scientific article; zbMATH DE number 1226875 (Why is no real title available?)
- On Fraïssé's conjecture for linear orders of finite Hausdorff rank
- Reverse mathematics and ordinal exponentiation
- Reverse mathematics and well-ordering principles: a pilot study
- Systems of predicative analysis
- The consistency of arithmetics
- The role of parameters in bar rule and bar induction
Cited in
(32)- Reverse mathematics and well-ordering principles: a pilot study
- Derivatives of normal functions and \(\omega \)-models
- Turing reducibility in the fine hierarchy
- Derivatives of normal functions in reverse mathematics
- \(\Pi_1^1\)-comprehension as a well-ordering principle
- Proof-theoretic strengths of the well-ordering principles
- Big vee: the story of a function, an algorithm, and three mathematical worlds
- The strength of Ramsey's theorem for coloring relatively large sets
- The reverse mathematics of wqos and bqos
- From hierarchies to well-foundedness
- Well-ordering Principles, ω-models and $$ \varPi_{1}^{1} $$-comprehension
- Well-Ordering Principles in Proof Theory and Reverse Mathematics
- Predicative collapsing principles
- Computable aspects of the Bachmann-Howard principle
- HOW STRONG ARE SINGLE FIXED POINTS OF NORMAL FUNCTIONS?
- WELL ORDERING PRINCIPLES AND -STATEMENTS: A PILOT STUDY
- PRIORITY ARGUMENTS VIA TRUE STAGES
- On the structure of the Wadge degrees of bqo-valued Borel functions
- Reducing ω-model reflection to iterated syntactic reflection
- Well ordering principles for iterated \(\Pi^1_1\)-comprehension
- A note on ordinal exponentiation and derivatives of normal functions
- On the logical strength of the better quasi order with three elements
- Functorial Fast-Growing Hierarchies
- The Π21\Pi ^1_2 consequences of a theory
- Iterated priority arguments in descriptive set theory
- Higman's lemma is stronger for better quasi orders
- Weak well orders and Fraïssé's conjecture
- Reflection ranks via infinitary derivations
- On inverse Goodstein sequences
- A one-page proof of a theorem of Beleznay
- Fraïssé's conjecture, partial impredicativity and well-ordering principles. I
- Reductions of well-ordering principles to combinatorial theorems
This page was built for publication: The Veblen functions for computability theorists
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3011121)
