Categorical characterizations of the natural numbers require primitive recursion

Simpson and Yokoyama (2013) [9] asked whether there exists a characterization of the natural numbers by a second-order sentence which is provably categorical in the theory RCA0⁎. We answer in the negative, showing that for any characterization of the natural numbers which is provably true in WKL0⁎, the categoricity theorem implies Σ10 induction.On the other hand, we show that RCA0⁎ 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 Π21-conservative extension of RCA0⁎ admits a provably categorical single-sentence characterization of the naturals, but each such characterization has to be inconsistent with WKL0⁎+superexp.