Computable aspects of the Bachmann-Howard principle

DOI10.1142/S0219061320500063MaRDI QIDQ5118047zbMATH OpenOpenAlexFDO

Authors Anton Freund

Publication date 4 September 2020

Published in Journal of Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.06774

zbMATH Keywords

reverse mathematicswell-ordering principlesdilators\(\Pi^1_1\)-comprehensionnotation systemBachmann-Howard fixed pointsATR\(_0\)

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Recursive ordinals and ordinal notations (03F15)

Abstract: We have previously established that $P{i}_1^1$-comprehension is equivalent to the statement that every dilator has a well-founded Bachmann-Howard fixed point, over $mathbfAT{R}_0$. In the present paper we show that the base theory can be lowered to $mathbfRC{A}_0$. We also show that the minimal Bachmann-Howard fixed point of a dilator $T$ can be represented by a notation system $vartheta(T)$, which is computable relative to $T$. The statement that $vartheta(T)$ is well-founded for any dilator $T$ will still be equivalent to $P{i}_1^1$-comprehension. Thus the latter is split into the computable transformation $Tmapstovartheta(T)$ and a statement about the preservation of well-foundedness, over a system of computable mathematics.

Recommendations

• A categorical construction of Bachmann–Howard fixed points
• \(\Pi_1^1\)-comprehension as a well-ordering principle
• HOW STRONG ARE SINGLE FIXED POINTS OF NORMAL FUNCTIONS?
• The Bachmann-Howard structure in terms of _1-elementarity
• Predicative collapsing principles

Cites work

• scientific article; zbMATH DE number 6536275 (Why is no real title available?)
• scientific article; zbMATH DE number 4033738 (Why is no real title available?)
• scientific article; zbMATH DE number 4039890 (Why is no real title available?)
• scientific article; zbMATH DE number 3349789 (Why is no real title available?)
• A categorical construction of Bachmann–Howard fixed points
• A proof-theoretic characterization of the primitive recursive set functions
• Logic colloquium '80. Papers intended for the European Summer Meeting of the Association for Symbolic Logic, held in Prague, August 24-30, 1980
• Open questions in reverse mathematics
• Proof-theoretic investigations on Kruskal's theorem
• Reverse mathematics and ordinal exponentiation
• Reverse mathematics and well-ordering principles
• Reverse mathematics and well-ordering principles: a pilot study
• Subsystems of second order arithmetic
• The Veblen functions for computability theorists
• Well-ordering principles and bar induction
• \(\Pi_1^1\)-comprehension as a well-ordering principle
• Π12-logic, Part 1: Dilators

Cited in

(16)

• WELL ORDERING PRINCIPLES AND -STATEMENTS: A PILOT STUDY
• Predicative collapsing principles
• Minimal bad sequences are necessary for a uniform Kruskal theorem
• Ackermann and Goodstein go functorial
• On the computational content of the Bolzano-Weierstraß Principle
• HOW STRONG ARE SINGLE FIXED POINTS OF NORMAL FUNCTIONS?
• A categorical construction of Bachmann–Howard fixed points
• A note on ordinal exponentiation and derivatives of normal functions
• Well-Ordering Principles in Proof Theory and Reverse Mathematics
• From Kruskal’s theorem to Friedman’s gap condition
• Bachmann-Howard derivatives
• Well ordering principles for iterated \(\Pi^1_1\)-comprehension
• Patterns of resemblance and Bachmann-Howard fixed points
• \(\Pi_1^1\)-comprehension as a well-ordering principle
• An order-theoretic characterization of the Howard-Bachmann-hierarchy
• Derivatives of normal functions in reverse mathematics

This page was built for publication: Computable aspects of the Bachmann-Howard principle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5118047)