Computable aspects of the Bachmann–Howard principle

DOI10.1142/S0219061320500063zbMATH Open1457.03027arXiv1809.06774OpenAlexW3102088491MaRDI QIDQ5118047FDOQ5118047

Anton Freund

Publication date: 4 September 2020

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A proof-theoretic characterization of the primitive recursive set functions
• Open Questions in Reverse Mathematics
• Proof-theoretic investigations on Kruskal's theorem
• Reverse mathematics and well-ordering principles
• The Veblen functions for computability theorists
• Reverse mathematics and ordinal exponentiation
• Π12-logic, Part 1: Dilators
• Reverse mathematics and well-ordering principles: a pilot study
• Logic colloquium '80. Papers intended for the European Summer Meeting of the Association for Symbolic Logic, held in Prague, August 24-30, 1980
• Well-Ordering Principles and Bar Induction
• \(\Pi_1^1\)-comprehension as a well-ordering principle
• A categorical construction of Bachmann–Howard fixed points

Cited In (15)

• WELL ORDERING PRINCIPLES AND -STATEMENTS: A PILOT STUDY
• Ackermann and Goodstein go functorial
• Minimal bad sequences are necessary for a uniform Kruskal theorem
• HOW STRONG ARE SINGLE FIXED POINTS OF NORMAL FUNCTIONS?
• On the computational content of the Bolzano-Weierstraß Principle
• 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
• PREDICATIVE COLLAPSING PRINCIPLES
• \(\Pi_1^1\)-comprehension as a well-ordering principle
• 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)