Reverse mathematics and Peano categoricity (Q1935867)

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)].