# Does induction axiom really forbid "rogue" elements in natural numbers?

I've checked formulation of Peano arithmetic second order induction axiom in several books and everywhere it is +- the same:

Let $$P (n)$$ be any property pertaining to a natural number n. Suppose that P (0) is true, and suppose that whenever P (n) is true, $$P (n++)$$ is also true. Then $$P (n)$$ is true for every natural number $$n$$.

I have checked this discussion A question on Terence Tao's representation of Peano Axioms but I still can't accept arguments from top rated answer because as for me it is actually still possible that there exist such natural numbers $$a,b$$ and $$c$$: a++ = b, b++ = c, c++ = a. After all this axiom only states that if some predicate $$P$$ satisfies the requirements from the axiom then I can say that $$P(n)$$ is true for every natural number and I understand intuition behind this axiom that $$P(0)$$ $$\implies$$ P(0++) $$\implies$$ P((0++)++) $$\ldots$$ so that it is true for all increments of 0, but I don't see in the formulation of axiom any explicit restrictions for what natural number can be. However, this formulation is used everywhere, so most likely I just do not understand something... moreover I am quite new to logic. Could you please explain to me where I'm wrong?

Addition to question: I will outline the big picture as I see it. I assume that "true" natural numbers exist, but I would like to have a strict formal description of them in the form of a system of axioms. Such a system is Peano's system of axioms. I know that Peano's system of axioms is categorical. I also know that these axioms have been proven consistent within the ZFC axiom system. The last piece of the puzzle for me is the answer to the question: do these axioms really describe "true" natural numbers and only them? You propose to consider the predicate "not to be rogue", but this is a rather vague formulation of the predicate, I do not understand what is hidden behind it, so I do not quite trust the proof using it. An acceptable proof for me would be 1) to prove that all properties of "true" natural numbers follow from Peano's axioms 2) to prove that properties that "true" natural numbers do not have do not follow from these axioms (it is the violation of this point that should lead to the appearance of "rogue" natural numbers). I accept the 1st point, but not the 2nd point. In order to consider the 2nd point satisfied, I must be sure that whatever predicate that gives false for "true" natural numbers I take, I must be able to prove its falsity using Peano's axioms. The catch is that there are infinitely many such predicates, so you need to use some more "low-level" methods to prove it. And at this point I'm stuck, I don't know what results to rely on to prove to myself that this 2nd point is true.

• claim: no natural number is equal to a, b, or c. Proof: by induction. Base: a, b, c, can't be 0 since they are all successors. Step: suppose x is not a, b, c. S(x) can't be a because then S(x) = S(c), so x=c, contradicting the inductive hypothesis. Similarly S(x) is not b or c. Mar 25 at 20:35
• @MatthewTowers thank you for your comment. Actually the point is not in this particular case with a, b, c. My question is about such all possible cases with "rogue" elements. Do I understand correctly that you mean that the purpose of induction axiom is to give a way to prove all possible predicates that don't contradict other Peano axioms for all natural numbers? Mar 25 at 21:19
• Consider applying induction to the property "is not a rogue element." Mar 25 at 22:06
• @NoahSchweber as far as I understand Peano axioms define what natural number is, so it seems to me that the whole point of induction axiom is just to give opportunity to prove or disprove any proposition for all natural numbers based on other Peano axioms. Otherwise property "is not a rogue element" is quite vague. Mar 25 at 22:20
• @user341 I don't really understand your question, to be honest. If "rogue-ness" is vague, then it makes no sense to ask your question in the first place; if "rogue-ness" is not vague, then we can apply induction to the property "is not rogue." And we can leave the term "rogue" behind: if you are comfortable with the idea of "true" $\mathbb{N}$ existing at the outset it should be easy to see that second-order PA is totally categorical. For a model $M$ of second-order PA consider the property "is in the image of the unique embedding of $\mathbb{N}\rightarrow M$" (this is just "non-roguishness"). Mar 25 at 23:37

You wrote:

I don't see in the formulation of axiom any explicit restrictions for what natural number can be.

Here are some well known, supposedly self-evident properties of the natural numbers:

1. $$0$$ is a natural number
2. Every natural number has a unique successor that is a natural number
3. Different natural numbers have different successors
4. $$0$$ is not the successor of any natural number
5. Every natural number but $$0$$ itself can be reached by a process of repeated succession starting at $$0$$

These properties of the natural numbers can be formalized respectively in the language of set theory as follows (Peano's Axioms for $$(N,S,0))$$:

1. $$0\in N$$
2. $$\forall x\in N: S(x) \in N$$
3. $$\forall x, y \in N: [S(x)=S(y) \implies x=y]$$
4. $$\forall x \in N: S(x)\neq 0$$
5. $$\forall P\subset N:[0\in P \land \forall x\in P:[S(x)\in P] \implies P=N]$$

Where

$$N$$ = the set of natural numbers

$$S$$ = the successor function on $$N$$

(1) through (4) here are straightforward translations. (5) may be not be so obvious. For what it is worth, here is formal proof (228 lines) of this equivalence for the skeptics.

Are we missing anything? Maybe some other essential properties of the natural numbers? It seems unlikely that additional axioms will be required since every algebraic system that satisfies Peano's Axioms as listed above will essentially be the be the same system, only the names will differ.

Informally, we can match up the elements of $$N$$ and $$N'$$ quite naturally as follows:

$$0 \longleftrightarrow 0'$$

$$S(0) \longleftrightarrow S'(0)$$

$$S(S(0)) \longleftrightarrow S'(S'(0'))$$

$$\vdots$$

This matching up would be uniquely given by the function f mapping $$N$$ to $$N'$$ such that:

$$f: N\to N'$$

$$f(0)=0'$$

$$\forall a\in N: f(S(a))=S'(f(a))$$

Not for the faint of heart, you can find formal proof of this here (723 lines).

• Thanks for the detailed answer, Dan! I would like to clarify one last thing before closing the question. Do I understand correctly that this proof is built on the basis of ZFC axioms? Mar 28 at 1:11
• Not exactly. It is based on what might be called a simplified, more user-friendly version of ZFC. It is robust enough to avoid the contradictions that arise, for example, from Russell's Paradox. Mar 28 at 2:13

Axiom 2.3 ensures $$0$$ is not the successor of another number. Define $$s^0=0$$ and $$s^{n+1}=s^n++$$ and assume $$s^{n}$$ is the first element to be repeated. That is to say there exists some chain $$s^{n-1} \rightarrow s^n \rightarrow \dots \rightarrow s^{n+k} \rightarrow s^n$$. This means $$s^{n-1}$$ and $$s^{n+k}$$ have the same successor contradicting axiom 2.4. From that we can conclude no elements are repeated.

Note that I've tacitly used induction here. I check that $$0$$ isn't a rogue element and then use the fact $$s^{n}$$ is the successor of some other number to finish the proof. Also, because you're building understanding I decided to use counting notation even though counting hasn't technically been defined yet. Some familiarity can improve understanding when working this close to the axioms.

• @DanChristensen obviously if you change the axioms you get different results but I don't what your point is. Mar 26 at 11:16
• Deleted my comment. Mar 26 at 15:56