Categorical characterizations of the natural numbers require primitive recursion

Abstract

Simpson and the second author asked whether there exists a characterization of the natural numbers by a second-order sentence which is provably categorical in the theory RCA${}_0^{\ast }$. We answer in the negative, showing that for any characterization of the natural numbers which is provably true in WKL${}_0^{\ast }$, the categoricity theorem implies ${\Sigma }_1^0$ induction. On the other hand, we show that RCA${}_0^{\ast }$ does make it possible to characterize the natural numbers categorically by means of a set of second-order sentences. We also show that a certain ${\Pi }_2^1$-conservative extension of RCA${}_0^{\ast }$ admits a provably categorical single-sentence characterization of the naturals, but each such characterization has to be inconsistent with WKL${}_0^{\ast }$+superexp.

17 pages