# Role of Induction among Peano Axioms

I am working with Peano Axioms as follows:

1. $$0 \in \mathbb{N}$$.
2. $$n \in \mathbb{N} \implies S(n) \in \mathbb{N}$$.
3. $$(\forall n \in \mathbb{N})(S(n) \neq 0)$$.
4. $$n \neq m \implies S(n) \neq S(m)$$.
5. Let $$A$$ be a subset of $$\mathbb{N}$$. If $$0 \in A$$ and $$n \in A \implies S(n) \in A$$, then $$A = \mathbb{N}$$.

I would like to motivate the presence of axiom 5 by presenting an example in which there are unnecessary elements. For instance the set $$A = \{0,1,2,\star,3,4,...\}$$ such that $$\star \neq 0$$ and $$S(\star) = \star$$. As far as I can see set $$A$$ satisfies the first 4 axioms and fails the fifth. In order to prove this it should be sufficient to prove that no natural number is equal to its successor. Thus that $$\star$$ cannot belong to $$\mathbb{N}$$. A proof might look like this:

Let $$A$$ be the set of natural numbers that are not equal to their successor. By axiom 3 $$S(0) \neq 0$$. Thus $$0 \in A$$. Suppose $$n \in A$$. Thus $$S(n) \neq n$$. Suppose towards contradiction that $$S(S(n)) = S(n)$$. By axiom 4 this implies $$S(n) = n$$. Thus $$n$$ should not be in $$A$$. This is a contradiction. Thus $$S(S(n)) \neq S(n)$$. In other words $$n \in A \rightarrow S(n) \in A$$ and the induction is complete.

I would like to ask two things:

1. Is my example and proof valid?
2. What could be a more general example of unnecessary elements in $$\mathbb{N}$$ that are ruled out by axiom 5? There are of course infinitely many ways in which one can build a set which contains the naturals as a subset, I am looking for the most general example or reasoning one can make rather than my very particular one.
• The fifth axiom is for subsets of $\Bbb N$, not for general sets. Jul 15 at 18:30
• Does this question help, in particular Eric Wofsey's answer?
– Joe
Jul 15 at 20:53
• @JoséCarlosSantos. Do you mean that the fifth axiom is meant to avoid the possibility that subsets of $\mathbb{N}$ are confused with $\mathbb{N}$? Or do you mean that it should be stated in terms of subsets? If the first, could you explain why often (Tao, Analysis 1; Wikipedia) it is said that the fifth axiom denies the possibility of extra "rogue" elements? Jul 17 at 18:16
• What I mean is that the fifth axiom is this: if $A\subset\Bbb N$ is such that $0\in A$ and that, for each $n\in A$, $S(n)\in A$, then $A=\Bbb N$. And, yes, it prevents the existence of “rogue” elements. That is, it allows you to prove that every natural number is one of the numbers $0$, $S(0)$, $S\bigl(S(0)\bigr)$, and so on. In fact, if$$A=\left\{0,S(0),S\bigl(S(0)\bigr),\ldots\right\},$$then $0\in A$ and, for each $n\in A$, $S(n)\in A$. Therefore, $A=\Bbb N$. That is, there are no “rogue” elements in $\Bbb N$. Jul 17 at 18:23
• @JoséCarlosSantos Thanks for the answer. I understand that if the fifth axiom is just for subsets of $\mathbb{N}$, then everything follows as you say. I wonder why it is so often quoted without this specification. For instance, Wolfram mathworld, requires it to be just a set of numbers while Britannica does not include the specification at all. To conclude why would something like my set $A$ not qualify as $\mathbb{N}$? bacause it is provable (through axiom 5) that there cannot be any element like $\star$ among natural numbers? or for some different reason? Jul 17 at 18:49

## 1 Answer

The set $$A$$ you've given isn't even a subset of $$\mathbb{N}$$. Already by the way you defined $$S(*)=*$$ it is ruled out by second axiom since $$* \notin \mathbb{N}$$.

The most basic example of a set that would fail to satisfy the fifth axiom would be a set of all even numbers from $$\mathbb{N}$$ including a zero, $$A=\{2n|n\in\mathbb{N}\}\cup\{0\}$$.

• Maybe I explained myself incorrectly. I never wanted $A$ to be a subset of $\mathbb{N}$. I only wanted to know if something like $A$ would fail the fifth axiom. In particular I don't understand why something like it should fail axiom 2. As far as I understand things, Peano axioms here are meant to characterize the natural numbers. How do you even know that $*\notin \mathbb{N}$ if not through the axioms themselves? If $A$ has $*$ in it. And $S(*) = *$, then I don't see why it fails axiom 2. Could you expand? Jul 16 at 21:11