Reverse mathematics and Peano categoricity

DOI10.1016/J.APAL.2012.10.014MaRDI QIDQ1935867zbMATH OpenOpenAlexFDO

Authors Stephen G. Simpson, Keita Yokoyama

Publication date 19 February 2013

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2012.10.014

zbMATH Keywords

ADSDedekindfoundations of mathematicsinductive systemlinear orderingPeano systemproof theoryRCAreverse mathematicssecond-order arithmeticsecond-order logicWKL

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35)

Review text

The authors analyze the strength of a theorem of Dedekind characterizing Peano systems. The \textsl{system} \(A\), \(i\), \(f\) consists of a set \(A\), a designated element \(i \in A\), and a function \(f:A \to A\). A set \(X\subset A\) is \textsl{inductive} if \(i \in X\) and \(\forall a (a \in X \to f(a) \in X )\). In a \textsl{Peano system}, \(i\) is not in the range of \(f\) and the only inductive subset of \(A\) is \(A\) itself. The authors prove in \(\mathrm{RCA}_0\) that \(\mathrm{WKL}_0\) is equivalent to the assertion that every Peano system is isomorphic to the natural numbers. Consequently, this form of Dedekind's Peano categoricity theorem is finitistically reducible. Next, the authors prove the preceding equivalence in the weaker subsystem \(\mathrm{RCA}_0^*\), which restricts induction to \(\Delta^0_1\)-formulas and appends natural number exponentiation. This result shows that the construction of the isomorphism in the Peano categoricity theorem requires primitive recursion. Categoricity theorems for other orderings are also analyzed, including some results related to ADS, the ascending/descending sequence principle of \textit{D. R. Hirschfeldt} and \textit{R. A. Shore} [``Combinatorial principles weaker than Ramsey's theorem for pairs, J. Symb. Log. 72, No. 1, 171--206 (2007; Zbl 1118.03055)].

Recommendations

• Publication:4944903
• Investigations of subsystems of second order arithmetic and set theory in strength between \(\Pi^1_1\)-CA and \(\Delta^1_2\)-\(\text{CA}+\text{BI}\). I
• The uniform content of partial and linear orders
• scientific article; zbMATH DE number 1215495
• Predicative foundations of arithmetic
• Internal categoricity in arithmetic and set theory
• Variation on a theme of Schütte
• scientific article; zbMATH DE number 4016884
• Categorical characterizations of the natural numbers require primitive recursion
• A note on finiteness in the predicative foundations of arithmetic

Cited in

(15)

• Weaker cousins of Ramsey's theorem over a weak base theory
• On certain axiomatizations of arithmetic of natural and integer numbers
• Internal categoricity in arithmetic and set theory
• Baire categoricity and \(\Sigma_1^0\)-induction
• Reverse mathematical bounds for the termination theorem
• scientific article; zbMATH DE number 1223053 (Why is no real title available?)
• Categorical characterizations of the natural numbers require primitive recursion
• On the strength of Ramsey's theorem without \(\Sigma _{1}\)-induction
• Game with numbers and axioms: Peano-Dedekind systems
• The Borel complexity of isomorphism for o-minimal theories
• Reverse mathematics, Young diagrams, and the ascending chain condition
• Primitive recursive reverse mathematics
• Internal categoricity, truth and determinacy
• HOW STRONG IS RAMSEY’S THEOREM IF INFINITY CAN BE WEAK?
• On arithmetical numberings in reverse mathematics

This page was built for publication: Reverse mathematics and Peano categoricity

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