Definition by Induction of Natural Number Addition

Theorem

Let $\N$ be the natural numbers, defined as the minimal infinite successor set $\omega$.

For each $m \in \N$, let $s_m: \N \to \N$ be the mapping:

$\forall n \in \N: s_m \left({n}\right) = \begin{cases} m & : n = 0 \\ \left({s_m \left({x}\right)}\right)^+ & : n = x^+ \end{cases}$

where $x^+$ is the successor set of $x$.

Then:

$s_m \left({n}\right) = m + n$

where $m + n$ is defined as natural number addition.

This can be expressed as:

	\(\displaystyle \)	\(\displaystyle \forall m, n \in \N:\)	\(\displaystyle \)	\(\displaystyle m + 0\)	\(=\)	\(\displaystyle m\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({m + n}\right)^+\)	\(=\)	\(\displaystyle m + n^+\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Corollary

Thus the intuitive concept that $n^+ = n + 1$ is formally defined.

Proof

The initial statement holds by Natural Numbers are Elements of the Minimal Infinite Successor Set.

Let $s: \N \to \N$ be the mapping defined as:

$\forall n \in \N: s \left({x}\right) = n^+$

where $n^+$ is the successor set of $n$.

From the Recursion Theorem, the mapping $s_m: \N \to \N$ such that:

$\forall n \in \N: s_m \left({n}\right) = \begin{cases} m & : n = 0 \\ s \left({s_m \left({x}\right)}\right) & : n = x^+ \end{cases}$

exists and is unique.

From Minimal Infinite Successor Set Fulfils Peano Axioms we have that:

$\forall m, n \in \omega: s \left({m}\right) = s \left({n}\right) \implies m = n$

ensuring that the mapping $s$ is well-defined.

The corollary follows immediately.

$\blacksquare$

Sources

• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 13$: Arithmetic