Peano, simple induction

249 Views Asked by At

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$?

2

There are 2 best solutions below

0
On BEST ANSWER

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$").

2
On

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}$.