1. Peano Axioms
In this page, the Peano natural number system is treated as basic structure for the natural numbers. Later, when formal arithmetic is introduced, we will use a first-order language of arithmetic to introduce the theory of natural numbers.
There are at least two modern and axiomatic way to construct the natural number set. One is the Peano natural number system, which will be introduced here; another is more set-theoretic, via the notion of “inductive sets”.
The natural number set $\N$ is a set that satisfies the following axioms:
- PA1$0\in \N$.
- PA2There is a function $S\colon \N\to \N$, called the successor function; i.e., for each $x\in \N$, $S(x)\in \N$. $S(x)$ is also denoted by $x’$.
- PA3For all $x\in \N$, $x’\neq 0$; i.e., $0$ is not the successor of any natural number;
- PA4For all $x,y\in \N$, if $x\neq y$, then $x’\neq y’$;
- PA5Let $M\subseteq\N$. If $0\in M$ and for all $x$, $x\in M$ implies $x’\in M$, then $M=\N$.
Remark.
Some people exclude $0$ from $\N$ and rewrite PA1 by $1\in \N$. We admit $0\in \N$ here and in the following mathematical logic pages.
PA1 prevents $\N$ from being an empty set. PA2 introduces an inductive way to describe $x+1$ for $x\in \N$; for example, $0’=1$, $1’=2$, etc. PA3 prevents $\N$ from behaving as a finite cycle; for example, if we remove PA3, then the set $\{0,1,2\}$ by requiring $0’=1$, $1’=2$, but $2’=0$ is also a valid natural number set.
PA4 asserts that the successor function is injective on $\N$. PA5 requires that besides the elements that are obtained from $0$ by finitely many applications of successor, there are no extra elements in $\N$. This is exactly what the induction axiom rules out.
2. Mathematical Induction
Mathematical Induction (MI), also called the Principle of Induction, is a basic proof method for statements about natural numbers. The usual forms of induction on the natural numbers can be derived from the Peano axioms. Here we present the proof of the ordinary form, which is also the most commonly used one in mathematical logic:
Suppose a proposition related to natural numbers $P(n)$ satisfies that:
- $P(0)$ holds;
- If $P(k)$ holds for some $k\in \N$, then so do $P(k+1)$;
Then $P(n)$ holds for all $n\in \N$.
Proof. Define
$$M = \{n\in \N\colon P(n)\text{ holds}\}.
$$
Then $M\subseteq\N$.
Note that $M$ satisfies all conditions listed in PA5, so we immediately obtain $M=\N$. This means $P(n)$ holds for all $n\in \N$.
Before introducing another form of induction, an important proposition is required.
Every nonempty subset of $\N$ has a minimal element.
To be precise, given a nonempty set $A\subseteq \N$, there exists an element $x_0\in A$ such that for all $x\in A$, $x_0\leq x$.
Proof. Given a nonempty subset $A\subseteq \N$. Let $L =\{x\in \N\colon \text{$x$ is a lower bound of $A$}\}$ (Here $x$ a lower bound of $A$ means $x\leq y$ for all $y\in A$). It suffices to show that $L\cap A\neq \varnothing$.
Suppose $L\cap A=\varnothing$. Note that:
- $0\in L$, as $0$ is obviously a lower bound of $A$;
- If $x\in L$, then by $L\cap A=\varnothing$, $x\in A$, so $x<y$ for all $y\in A$. This means $x+1\leq y$ for all $y\in A$, and $x+1\in L$.
Therefore, by PA5, $L=\N$, and $A\cap L = A=\varnothing$, which contradicts with $A\neq \varnothing$. This implies $L\cap A\neq \varnothing$, as desired.
Another form is also called the Strong Induction or Complete Induction:
Suppose a proposition related to natural numbers $P(n)$ satisfies that:
- $P(0)$ holds;
- If for all $m>0$, $P(k)$ holds for all $k<m$, then so do $P(m)$;
Then $P(n)$ holds for all $n\in \N$.
Proof. Define
$$E =\{n\in \N\colon \text{$P(n)$ does not hold}\}.
$$
It suffices to show that $E$ is an empty set.
Suppose $E\neq\varnothing$. As $E\subseteq\N$, by Proposition 2.2, $E$ must contain a smallest number, say $m\in E$. Firstly, $m\neq 0$, as $P(0)$ holds. Then for all $k<m$, $P(k)$ holds. By condition 2, $P(m)$ holds and $m\notin E$, contradictory to $m\in E$.
This means $E=\varnothing$, as desired.
3. The Recursion Theorem
The (Dedekind) Recursion Theorem can be simply described by:
For a sequence $\{a_n\}_{n\in \N}$, if $a_0$ is given, and there exists a function $h$ such that $a_{n+1}=h(a_n, n)$ (sometimes $a_{n+1}=h(a_n)$) for all $n\in \N$, then the sequence $\{a_n\}_{n\in \N}$ is completely determined.
A more rigorous version is:
Given set $A$, $a\in A$, function $h\colon A\times \N\to A$, there exists a unique function $f\colon \N\to A$ such that
$$
f(0)=a,\quad f(n+1)=h(f(n),n).
$$
or, an even stronger one:
Given set $A$, function $g\colon \N^k\to \N$, $h\colon \N^{k+2}\to \N$, $n_1,\dots,n_k\in \N$, there exists a unique function $f\colon \N^{k+1}\to \N$ such that
f(n_1,\dots,n_k,0) &= g(n_1,\dots,n_k),\\
f(n_1,\dots,n_k,n+1) &= h(n_1,\dots,n_k,n,f(n_1,\dots,n_k,n)).\\
\end{aligned}\]
Remark.
For each fixed parameters $(n_1,\dots,n_k)$, then Equations 3.1 determine a unique sequence in $n$.
For detailed proof, please refer here.