# Is the statement “All numbers are counting numbers” independent of $PA$?

In his paper, "Completed versus Incomplete Infinity in Arithmetic" (look under "www.math.princeton.edu/$\sim$nelson/papers.html" under the subheading "Infinity"), the late Edward Nelson defines the notion of 'counting number' as follows:

0 is a counting number

if $y$ is a counting number, so is $y{'}$ [ $^{'}$ is the successor operation--my comment]

The next sentence reads as follows:

This is all that we assume about the notion, and in particular we do not postulate that all numbers are counting numbers.

On page 7 of this paper, Nelson refers to the postulate that all numbers are counting numbers as a "Platonic postulate". It seems clear from his paper that Nelson believes that "All numbers are counting numbers" is a postulate that is definitely false.

But is it? I believe that the following formal statement (rightly or wrongly--you decide) in the language of $PA$ captures the intuitive notion of the aforementioned statement:

$\alpha$: ($\forall$$x)(x$$\neq$0.$\supset$.($\exists$$y)(y^{'}= x)) (Note: \alpha was found by me in someone's class notes online.) Question: Is '\alpha' independent of PA? Suppose, to the contrary, that PA$$\vdash$$\alpha. Then the following question seemingly arises: If PA$$\vdash$$\alpha, does this make PA susceptible to the criticisms Nelson holds to concerning PA? If not, why not? • The statement \alpha is a consequence of PA (it is trivially proved by induction), but it is definitely weaker than the statement "all natural numbers are counting numbers" (which is problematic to formalize except by using second-order logic); \alpha just says that every nonzero number has a predecessor, not necessarily that numbers can be obtained inductively from zero and successor. – Gro-Tsen Dec 13 '16 at 13:04 • I love that article. Nelson is not defining a notion of counting number inside of the peano system, he is extending the peano system by introducing a new predicate C(x), calling it "x is a counting number," and subjecting it to a couple of axioms. But he does not subject C to anything like an induction axiom. Your proposition alpha is also true in this extension of the peano system (call it PA+C?), but you cannot use it to prove that for all x, C(x). – David Treumann Dec 13 '16 at 13:05 • @Gro-Tsen: How then would you properly formalize the statement "Every number is a counting number"? – Thomas Benjamin Dec 13 '16 at 14:03 • @Gro-Tsen: of course, if we extend the language of PA with a unary relation symbol such as C that is true for counting numbers, then we can write a single axiom "C0 \land (\forall y)(Cy \to C(Sy))" to express Nelson's axioms, and we could write a single first-order induction axiom involving C that implies all naturals are counting numbers. So there is no essential use of second-order logic, just in case some other readers wonder about that. – Carl Mummert Dec 16 '16 at 12:39 • @David Treumann: the deeper question is why C(x) would not be subject to an induction axiom, of course. Nelson does manage to find a delicate balance, but the usual intuition that the natural numbers are the smallest set of a certain kind suggests that there should be an induction axiom for C as well. – Carl Mummert Dec 16 '16 at 12:41 ## 1 Answer The statement asserting that every number is a counting number is \forall n\ C(n), and this is definitely independent of PA, if PA is understood to include induction only in the usual language of arithmetic, without the predicate C. To see this, we can simply observe that the statement is true in the standard model of arithmetic, but in any non-standard model of PA, we may take C(x) to hold of exactly the standard numbers, and these satisfy the property about counting numbers that you mentioned. Indeed, one can take the counting numbers to be those in any closed-under-successor cut of a nonstandard model of PA. If one wants to subject the predicate C to the induction scheme, however, then it is clear that every number will be a counting number, by induction. In particular, in second-order PA we will be able to prove that every number is a counting number. Meanwhile, the perspective of the argument above suggests that we may imagine the counting numbers of Nelson to be referring to a possibly proper cut in the natural numbers, but the cut is not definable in the language of arithmetic or in any language in which we have induction. • Would it be fair to say that models of PA + (\exists$$x$) $\lnot$$C(x) would be models in which a type of Ultrafinitism holds? – Thomas Benjamin Dec 13 '16 at 13:59 • Yes, I think that this view resonates with many features of ultrafinitism. – Joel David Hamkins Dec 13 '16 at 14:08 • I find your statement , "In particular, in second-order arithmetic, [we are] able to prove that every number is a counting number.", very interesting from the perspective of reverse mathematics. If Gro-Tsen in correct in saying that the 'correct' formalization of "Every number is a counting number" in second-order arithmetic is just the second-order induction axiom, then what happens to Nelson's theorem, "...there does not exist a property p for which it is possible to prove that that if p(x ) then x is a counting number and that if p( x) and p( z) then – Thomas Benjamin Dec 14 '16 at 10:12 • (cont.) p(x$$\uparrow$$z$)? I am now wondering, what is the subsystem of second-order arithmetic 'closest' to second-order arithmetic in the "Goedel Hierarchy" in which Nelson's theorem holds, after which it fails (I know you said (essentially) that you are not a 'reverse mathematician', but I believe the question I asked does naturally arise given your's and Gro-Tsen's comments. Practitioners of reverse mathematics--feel free to weigh in....) – Thomas Benjamin Dec 14 '16 at 10:21
• @Thomas Benjamin: Nelson's paper extends the language of PA but doesn't change the induction scheme. So in a reverse mathematics context we would have to ask whether the set existence scheme is adjusted for the new language. If it is, then we could form the set $N = \{ x : C(x)\}$ as an instance of quantifier-free comprehension, and then prove $N$ contains all the numbers using Nelson's axioms for $C$ and using quantifier-free induction. On the other hand, if we cannot form the set $N$ then we will not be able to prove anything about it. The issue is precisely whether $N$ is definable. – Carl Mummert Dec 16 '16 at 12:45