# Peano, simple induction

I have the axiom from Peano's axioms:

If $A\subseteq \mathbb{N}$ and $1\in A$ and $m\in A \Rightarrow S(m)\in A$, then $A=\mathbb{N}$.

My book tells me that it secures that there are no more natural numbers than the numbers produced by the below 3 axioms (also from Peano's axioms):

$1\in \mathbb{N}$

For every $n\in\mathbb{N}: 1\neq S(n)$

For every $m,n\in \mathbb{N}:m\neq n\Rightarrow S(m) \neq S(n)$

And I'm not sure why? Is there someone who can explain this?

S(n) is an unary function $S: \mathbb N \rightarrow \mathbb N$. Does this means that $S(n)=n+1$?

-

Yes, $S(n)$ is intended to represent $n+1$. Later, when addition is defined, "$n+1$" will turn out to mean $S(n)$.

As for the induction: Let $$A=\{1,S(1),S(S(1)), S(S(S(1))),\ldots\}$$ This is clearly a subset of $\mathbb{N}$ as defined by the axioms; it satisfies $1\in A$ and for every $n\in A$ it must also be that $S(n)\in A$. Therefore, by the induction axiom, $A=\mathbb N$, so $$\mathbb N=\{1,S(1),S(S(1)), S(S(S(1)),\ldots\}$$

Strictly speaking the above argument is not quite formal, because formulas that involve "$\ldots$" are usually taken to be abbreviations for more involved constructions that involve the natural numbers. However, as our main aim here is to define the natural numbers formally in the first place, it is not clear that the above argument has any formal content at all. (It does, however: It says that whenever we have a model of the (second-order) Peano axioms, the model has to be isomorphic to the natural numbers we use at the metalevel to give meaning to the "$\ldots$").

-

The three axioms guarantee you that the set $A=\{1,S(1),S(S(1)),S(S(S(1))),...\}$ is infinite (mainly because of the injectivity of $S$). But they do not guarantee the equality $A=\mathbb{N}$. To set it you need the axiom of induction.

For example, put $S(n)=2n$. It satisfies the three axioms, but $A=\{1\}\cup\{2^n:\ n\in\mathbb{N}\}$, so there are natural numbers which cannot be obtained using only the three axioms.

The axiom of induction guarantees you that when $A$ is defined as above then $A=\mathbb{N}$.

-
But the set $A$ together with the function $S$ does satisfy Peano's axioms. It's another model of the axioms (that happens to be sitting inside the "standard model"). I'm not sure if that is a good example... –  Arturo Magidin Oct 19 '11 at 16:26
@Arturo: I see your point. The pair $(A,S)$ satisfies Peano's axioms and we can cosider it as a model of them, but the OP asks about something a bit different. The OP's question was: why does the axiom of induction secure that there are no other natural numbers than those in the set $A$ obtained from the first three axioms. My example shows that without the axiom of induction there is a model of natural numbers with the set $A$ different than $\mathbb{N}$. Adding the axiom of induction to my example is the same like saying that objects not from $A$ aren't natural numbers. This is how I see it. –  Damian Sobota Oct 19 '11 at 16:57