Reverse mathematics and Peano categoricity
type: Item
instance of: scholarly article
title: Reverse mathematics and Peano categoricity
zbMATH Open document ID: 1267.03030
author: Stephen G. Simpson
author: Keita Yokoyama
published in: Annals of Pure and Applied Logic
publication date: 2013-02-19T00:00:00Z
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)].
Mathematics Subject Classification ID: 03B30
Mathematics Subject Classification ID: 03F35
zbMATH DE Number: 6137400
zbMATH Keywords: reverse mathematics
zbMATH Keywords: second-order arithmetic
zbMATH Keywords: Peano system
zbMATH Keywords: foundations of mathematics
zbMATH Keywords: proof theory
zbMATH Keywords: second-order logic
zbMATH Keywords: RCA
zbMATH Keywords: WKL
zbMATH Keywords: inductive system
zbMATH Keywords: ADS
zbMATH Keywords: linear ordering
zbMATH Keywords: Dedekind
reviewed by: Jeffry L. Hirst
MaRDI profile type: Publication
full work available at URL: j.apal.2012.10.014
OpenAlex ID: W2066300600
DOI: 10.1016/J.APAL.2012.10.014
Recommended article: Q4944903
Recommended article: Q3081650
Recommended article: The uniform content of partial and linear orders
Recommended article: Q4215632
Recommended article: Predicative foundations of arithmetic
Recommended article: Internal categoricity in arithmetic and set theory
Recommended article: Variation on a theme of Schütte
Recommended article: Q3028996
Recommended article: Categorical characterizations of the natural numbers require primitive recursion
Recommended article: A note on finiteness in the predicative foundations of arithmetic
description: scientific article; zbMATH DE number 6137400