Categorical characterizations of the natural numbers require primitive recursion

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$. We answer in the negative, showing that for any characterization of the natural numbers which is provably true in WKL$^*_0$, the categoricity theorem implies $Sigma^0_1$ induction. On the other hand, we show that RCA$^*_0$ 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^1_2$-conservative extension of RCA$^*_0$ admits a provably categorical single-sentence characterization of the naturals, but each such characterization has to be inconsistent with WKL$^*_0$+superexp.

A generalization of Levin-Schnorrs theorem

In this paper, we will generalize the definition of partially random or complex reals, and then show the duality of random and complex, i.e., a generalized version of Levin-Schnorrs theorem. We also study randomness from the view point of arithmetic using the relativization to a complete $Pi^0_1$-class.