 # The Natural Numbers and the Principle of Induction

This unit introduces the natural numbers in the context of the axiomatics of Zermelo and Fraenkel.

The present unit is part of the following walks

## Introduction

In the following you will find a short summary of this unit. For detailed information please see the full text or download the pdf-document at the end of this page.

The present unit is the eighth and last unit of the walk The Axioms of Zermelo and Fraenkel. Based on the axioms of Zermelo and Fraenkel we will formally introduce the natural numbers.

At the same time this unit is the first unit of the Walk Numbers [in preparation] introducing the natural numbers, the integers, the rational, the real and the complex numbers and the quaternions.

You will learn the meaning of the following terms:

The main results are

In addition we will explain the the definition of natural numbers by Richard Dedekind according to bis famous article Was sind und was sollen die Zahlen?

## The Definition of the Natural Numbers

The definition of the natural numbers will be based on the so-called Peano sets explained in Unit Successor Sets and the Axioms of Peano.

Definition. Let $\omega$ be the minimal successor set, that is, the Peano set such that

$$0 := \emptyset \mbox{ and } A^+ := A \cup \{A\} \mbox{ for all } A \in \omega$$

The set $\omega$ is called the set of the natural numbers and is denoted by $\mathbb{N}_0$.

French / German. Set of the natural numbers = Ensemble des entiers naturels = Menge der natürlichen Zahlen.

Definition. (a) We set

\begin{eqnarray*}
1 & := & 0^+ = 0 \cup \{0\} = \{0\} = \{ \emptyset \} \\
2 & := & 1^+ = 1 \cup \{1\} = \{ 0, 1 \} = \big\{ \emptyset, \{ \emptyset \} \big\} \\
3 & := & 2^+ = 2 \cup \{2\} = \{0, 1, 2 \} = \big\{ \emptyset, \{ \emptyset \}, \big\{ \emptyset, \{ \emptyset \} \big\} \big\} \\
& \ldots &\\
1437 & := & 1436^+ = 1436 \cup \{1436\} = \{0, 1, \ldots, 1436 \} \\
& \ldots &
\end{eqnarray*}

using the decimal number system without further explanation. The above defined numbers are called natural numbers.

(b) For each natural number $n$, we set $n + 1 := n^+$.

(c) We denote by $\mathbb{N} := \mathbb{N}_0 \setminus \{0\}$ the set of the natural numbers without the number $0$.

French / German. Natural number = Entier naturel = Natürliche Zahl.

Note that the number $0$ is defined to be a natural number. Some authors do define the number $0$ to be natural, others don’t. We follow Bourbaki.

## The Principle of Induction and the Recurisive Definition of Functions

Theorem. (Principle of Induction) Suppose that $(A_n)_{n \in \mathbb{N}_0}$ is a family of sentences with the following properties:

(i) $n = 0$: The sentence $A_0$ is true.

(ii) $n \mapsto n + 1$: If the sentence $A_n$ is true, then the sentence $A_{n + 1}$ is also true.

Then every sentence of the family $(A_n)_{n \in \mathbb{N}_0}$ is true.

Definition. The principle stated in Theorem [#nst-th-principle-induction] is called the principle of induction. It is denoted by:

$n = 0$: Show that the sentence $A_0$ is true.

$n \mapsto n + 1$: Show that the sentence $A_n$ implies the sentence $A_{n + 1}$.

Then one can conclude that the sentence $A_n$ is true for all natural numbers $n$.

Note that the principle of induction can also be applied on the set $\mathbb{N}$. In this case, we consider the cases $n = 1$ and $n \mapsto n + 1$.

French / German. Principle of induction = Raisonnement par récurrence = Prinzip der vollständigen Induktion.

Remark. Note that the principle of induction is not a principle of logical deduction but simply a theorem.

Theorem. (Recursive Definition of a Function) Let $X$ be a non-empty set, let $f : X \rightarrow X$ be a function from the set $X$ into itself, and let $a$ be an element of the set $X$.

Then there exists exactly one function $\alpha : \mathbb{N}_0 \rightarrow X$ from the set $\mathbb{N}_0$ into the set $X$ fulfilling the following conditions:

(i) We have $\alpha(0) = a$.

(ii) We have $\alpha(n + 1) = f( \alpha(n) )$ for each natural number $n$.

French / German. Recursive definition of a function = Définition d’une fonction par récurrence = Rekursive Definition einer Funktion.

## The Addition of Natural Numbers

In this section we will introduce the addition of natural numbers:

Proposition. Let $m$ be a natural number. Then there exists exactly one function

$$\alpha_m : \mathbb{N}_0 \rightarrow \mathbb{N}_0$$

from the set $\mathbb{N}_0$ into itself such that

\begin{equation}
\alpha_m(0) = m \mbox{ and } \alpha_m(n + 1) = \alpha_m(n) + 1 \mbox{ for all } n \in \mathbb{N}_0.
\end{equation}

Definition. Let $m$ and $n$ be two natural numbers, and let $\alpha_m : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ be the function from the set $\mathbb{N}_0$ into itself defined in Proposition [#nst-prop-addition-recursion]. Set

\begin{equation}
m + n := \alpha_m(n).
\end{equation}

The operation

$$+ : \mathbb{N}_0 \times \mathbb{N}_0 \rightarrow \mathbb{N}_0, (m, n) \mapsto m + n$$

is called the addition of natural numbers. The element $m + n$ is called the sum of the natural numbers $m$ and $n$.

French / German. Addition of natural numbers = Addition des entiers naturels = Addition natürlicher Zahlen. Sum = Somme = Summe.

Theorem. The addition in the set $\mathbb{N}_0$ is associative, that is, we have

\begin{equation}
(k + m) + n = k + (m + n) \mbox{ for all } k, m, n \in \mathbb{N}_0.
\end{equation}

Theorem. The addition in the set $\mathbb{N}_0$ is commutative, that is, we have

\begin{equation}
m + n = n + m \mbox{ for all } m, n \in \mathbb{N}_0.
\end{equation}

Theorem. Let $x$, $m$ and $n$ be three natural numbers.

(a) If $x + m = x + n$, then we have $m = n$.

(b) If $m + x = n + x$, then we have $m = n$.

(c) If $m + n = 0$, then we have $m = 0$ and $n = 0$.

Theorem. Let $m$ and $n$ be two natural numbers. Then exactly one of the following cases occurs:

(i) We have $n = m$.

(ii) There exists a natural number $k \neq 0$ such that $n = m + k$.

(iii) There exists a natural number $k \neq 0$ such that $m = n + k$.

## The Multiplication of Natural Numbers

In this section we will introduce the multiplication of natural numbers:

Proposition. Let $m$ be a natural number. Then there exists exactly one function

$$\beta_m : \mathbb{N}_0 \rightarrow \mathbb{N}_0$$

from the set $\mathbb{N}_0$ into itself such that

\begin{equation}
\beta_m(0) = 0 \mbox{ and } \beta_m(n + 1) = \beta_m(n) + m \mbox{ for all } n \in \mathbb{N}_0.
\end{equation}

Definition. Let $m$ and $n$ be two natural numbers, and let $\beta_m : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ be the function from the set $\mathbb{N}_0$ into itself defined in Proposition [#nst-prop-multiplication-recursion]. Set

\begin{equation}
m \cdot n := \beta_m(n).
\end{equation}

The operation

$$\cdot : \mathbb{N}_0 \times \mathbb{N}_0 \rightarrow \mathbb{N}_0, (m, n) \mapsto m \cdot n$$

is called the multiplication of natural numbers. The element $m \cdot n$ is called the product of the natural numbers $m$ and $n$. We often write $mn$ instead of $m \cdot n$.

French / German. Multiplication of natural numbers = Multiplication des entiers naturels = Multiplikation natürlicher Zahlen. Product = Produit = Produkt.

Theorem. The multiplication in the set $\mathbb{N}_0$ is associative, that is, we have

\begin{equation}
(k m) n = k (m n) \mbox{ for all } k, m, n \in \mathbb{N}_0.
\end{equation}

Theorem. The multiplication in the set $\mathbb{N}_0$ is commutative, that is, we have

\begin{equation}
m n = n m \mbox{ for all } m, n \in \mathbb{N}_0.
\end{equation}

Theorem. The distributive laws hold in the set $\mathbb{N}_0$, that is:

(a) We have

\begin{equation}
k (m + n) = k m + k n \mbox{ for all } k, m, n \in \mathbb{N}_0.
\end{equation}

(b) We have

\begin{equation}
(k + m) n = k n + m n \mbox{ for all } k, m, n \in \mathbb{N}_0.
\end{equation}

Theorem. Let $x$, $m$ and $n$ be three natural numbers.

(a) If $mn = 0$, then we have $m = 0$ or $n = 0$.

(b) If $mn = 1$, then we have $m = 1$ and $n = 1$.

(c) If $xm = xn$, then we have $x = 0$ or $m = n$.

(d) If $mx = nx$, then we have $x = 0$ or $m = n$.

## The Power of Natural Numbers

In this section we will introduce the exponentiation of natural numbers:

Proposition. Let $m$ be a natural number. Then there exists exactly one function

$$\gamma_m : \mathbb{N}_0 \rightarrow \mathbb{N}_0$$

from the set $\mathbb{N}_0$ into itself such that

\begin{equation}
\gamma_m(0) = 1 \mbox{ and } \gamma_m(n + 1) = \gamma_m(n) \cdot m \mbox{ for all } n \in \mathbb{N}_0.
\end{equation}

Definition. Let $m$ and $n$ be two natural numbers, and let $\gamma_m : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ be the function from the set $\mathbb{N}_0$ into itself defined in Proposition [#nst-prop-power-recursion]. Set

\begin{equation}
m^n := \gamma_m(n).
\end{equation}

The value $m^n$ is called the $n$th power of the number $m$. The operation $(m, n) \mapsto m^n$ is called exponentiation.

French / German. Power of a natural number = Puissance d’un entier naturel = Potenz einer natürlichen Zahl. Exponentiation = Exponentiation = Potenzieren (= Exponentiation).

Theorem. (a) We have

\begin{equation}
(km)^n = k^n \cdot m^n \mbox{ for all } k, m, n \in \mathbb{N}_0.
\end{equation}

(b) We have

\begin{equation}
k^{m + n} = k^m \cdot k^n \mbox{ for all } k, m, n \in \mathbb{N}_0.
\end{equation}

(c) We have

\begin{equation}
(k^m)^n = k^{mn} \mbox{ for all } k, m, n \in \mathbb{N}_0.
\end{equation}

Proposition. Let $x$, $m$ and $n$ be three natural numbers.

(a) If $x^m = 0$, then we have $m \neq 0$ and $x = 0$.

(b) If $x^m = 1$, then we have $m = 0$ or $x = 1$.

(c) If $x^m = x^n$, then we have $x = 0$ or $x = 1$ or $m = n$.

## Factorial of n and the Fibonacci Numbers

For the recursive definition of some functions the process described in Theorem [#nst-th-natural-numbers-recursion-theorem] has to be extended. We will present two examples, the factorial $n!$ of a natural number $n$ (see Example [#nst-ex-factorial]) and the Fibonacci numbers (see Example [#nst-ex-fibonacci]).

Example. The factorial $n!$ of a natural number $n$ is defined as follows:

$$0! := 1, \: n! := 1 \cdot 2 \cdot \ldots \cdot n \mbox{ for all } n \in \mathbb{N}.$$

For more details see the full text.

Example. The Fibonacci numbers $\big( F_n \big)_{n \in \mathbb{N}_0}$ are defined as follows:

$$F_0 := 1, \: F_1 := 1, \: F_{n+2} := F_n + F_{n+1} \mbox{ for all } n \in \mathbb{N}_0.$$

For more details see the full text.

## The Standard Order on the Natural Numbers

In tis section we define the standard order $0 \leq 1 \leq 2 \leq \ldots$ on the natural numbers:

Definition. Let $m$ and $n$ be two natural numbers. We set $m \leq n$ if and only if there exists a natural number $r$ such that

$$n = m + r.$$

The order $\leq$ is called the standard order on the set of the natural numbers.

French / German. Standard order on the natural numbers = Ordre naturel sur les nombres entiers = Standardordnung auf den natürlichen Zahlen.

Theorem. The pair $(\mathbb{N}_0, \leq)$ is a totally ordered set with respect to the standard order on the natural numbers.

Theorem. Let $A$ be a subset of the set $\mathbb{N}_0$. If the set $A$ is non-empty, then it has a minimal element.

Proposition. Let $a$, $b$, $c$ and $d$ be four natural numbers.

(a) If $a \leq c$ and $b \leq d$, then we have $a + b \leq c + d$.

(b) If $a < c$ and $b \leq d$, then we have $a + b < c + d$.

(c) If $a \leq c$ and $b < d$, then we have $a + b < c + d$.

Proposition. Let $x$, $m$ and $n$ be three natural numbers.

(a) If $x +m \leq x + n$, then we have $m \leq n$.

(b) If $x +m < x + n$, then we have $m < n$.

Proposition. Let $a$, $b$, $c$ and $d$ be four natural numbers.

(a) If $a \leq c$ and $b \leq d$, then we have $ab \leq cd$.

(b) If $a < c$, $b \leq d$ and $d \neq 0$, then we have $ab < cd$.

(c) If $a \leq c$, $b < d$ and $c \neq 0$, then we have $ab < cd$.

Proposition. Let $x$, $m$ and $n$ be three natural numbers.

(a) If $x \neq 0$ and $xm \leq xn$, then we have $m \leq n$.

(b) If $x \neq 0$ and $xm < xn$, then we have $m < n$.

Proposition. Let $x$, $y$, $m$ and $n$ be four natural numbers.

(a) If $x \leq y$, then we have $x^n \leq y^n$.

(b) If $n \neq 0$ and $x < y$, then we have $x^n < y^n$.

(c) If $x \neq 0$ and $m \leq n$, then we have $x^m \leq x^n$.

(d) If $x \neq 0$, $x \neq 1$ and $m < n$, then we have $x^m < x^n$.

(e) If $x \neq 0$, $x \leq y$ and $m \leq n$, then we have $x^m \leq y^n$.

(f) If $x \neq 0$ $x \neq 1$, $x < y$ and $m \leq n$, then we have $x^m < y^n$.

(g) If $x \neq 0$ $x \neq 1$, $x \leq y$ and $m < n$, then we have $x^m < y^n$.

Proposition. Let $x$, $y$, $m$ and $n$ be four natural numbers.

(a) If $n \neq 0$ and $x^n \leq y^n$, then we have $x \leq y$.

(b) If $x^n < y^n$, then we have $x < y$.

(c) If $x \neq 0$, $x \neq 1$ and $x^m \leq x^n$, then we have $m \leq n$.

(d) If $x \neq 0$ and $x^m < x^n$, then we have $m < n$.

Proposition. Let $x$, $y$, and $n$ be three natural numbers.

If $x^n = y^n$, then we have $n = 0$ or $x = y$.

## Generalized Arithmetic Laws

In this section we extend the associative, the commutative and the distributive laws to an arbitrary number of elements:

Definition. Let $m$ and $n$ be two natural numbers, let $I := \{m , m + 1, \ldots, n\}$, and let $x_j$ be a natural number for each element $j$ of the set $I$.

(a) If $m > n$, we set

$$\sum_{j=m}^n x_j := 0 \mbox{ (empty sum)}.$$

(b) If $m = n$, we set

$$\sum_{j=m}^m x_j := x_m.$$

(c) If $m < n$, we have $n > 0$, and there exists a natural number $n’$ such that $n = n’ + 1$. It follows that $m \leq n’$. We set

$$\sum_{j=m}^n x_j := \left( \sum_{j=m}^{n’} x_j \right) + x_n \mbox{ (recursive definition)}.$$

(d) We set

$$x_k + x_{k+1} + \ldots + x_n := \sum_{j=k}^n x_j.$$

Definition. Let $m$ and $n$ be two natural numbers, let $I := \{m , m + 1, \ldots, n\}$, and let $x_j$ be a natural number for each element $j$ of the set $I$.

(a) If $m > n$, we set

$$\prod_{j=m}^n x_j := 1 \mbox{ (empty product)}.$$

(b) If $m = n$, we set

$$\prod_{j=m}^m x_j := x_m.$$

(c) If $m < n$, we have $n > 0$, and there exists a natural number $n’$ such that $n = n’ + 1$. It follows that $m \leq n’$. We set

$$\prod_{j=m}^n x_j := \left( \prod_{j=m}^{n’} x_j \right) \cdot x_n \mbox{ (recursive definition)}.$$

(d) We set

$$x_k \cdot x_{k+1} \cdot \ldots \cdot x_n := \prod_{j=k}^n x_j.$$

Proposition. Let $k$, $m$ and $n$ be three natural numbers such that $k \leq m < n$, and let

$$x_k, x_{k+1}, \ldots, x_m, x_{m+1}, \ldots, x_n$$

be a sequence of natural numbers.

(a) We have

$$\Big( \sum_{j=k}^m x_j \Big) + \Big( \sum_{j=m+1}^n x_j \Big) = \sum_{j=k}^n x_j.$$

(b) We have

$$\Big( \prod_{j=k}^m x_j \Big) \cdot \Big( \prod_{j=m+1}^n x_j \Big) = \prod_{j=k}^n x_j.$$

Proposition. (Generalized Associative Law) Let $k$ and $n$ be two natural numbers with $k < n$, and let $x_{k+1}, \ldots, x_n$ be a sequence of natural numbers. In addition, let $r \geq 1$ be a natural number, and let $n_0, n_1, \ldots, n_r$ be a sequence of natural numbers such that

$$k = n_0 < n_1 < \ldots < n_r = n.$$

Let $r’$ be the natural number such that $r = r’ + 1$.

(a) We have

$$\sum_{i=0}^{r’} \Big( \sum_{j=n_i + 1}^{n_{i + 1}} x_j \Big) = \sum_{j=k+1}^n x_j.$$

(b) We have

$$\prod_{i=0}^{r’} \Big( \prod_{j=n_i + 1}^{n_{i + 1}} x_j \Big) = \prod_{j=k+1}^n x_j.$$

Proposition. (Generalized Commutative Law) Let $x_1, \ldots, x_n$ be a sequence of natural numbers for some natural number $n \geq 1$, and let

$$\alpha : \{ 1, \ldots, n \} \rightarrow \{ 1, \ldots, n \}$$

be a bijective mapping from the set $\{ 1, \ldots, n \}$ onto itself.

(a) We have

$$x_{\alpha(1)} + \ldots + x_{\alpha(n)} = x_1 + \ldots + x_n.$$

(b) We have

$$x_{\alpha(1)} \cdot \ldots \cdot x_{\alpha(n)} = x_1 \cdot \ldots \cdot x_n.$$

(c) Let $y_1, \ldots, y_n$ be a sequence of natural numbers. Then we have

$$\sum_{i=1}^n \big( x_i + y_i \big) = \Big( \sum_{i=1}^n x_i \Big) + \Big( \sum_{i=1}^n y_i \Big) \mbox{ and } \prod_{i=1}^n \big( x_i y_i \big) = \Big( \prod_{i=1}^n x_i \Big) \cdot \Big( \prod_{i=1}^n y_i \Big)$$

Proposition. (Generalized Distributive Law) Let $x_1, \ldots, x_m$ and $y_1, \ldots, y_n$ be two sequences of natural numbers for some natural numbers $m \geq 1$ and $n \geq 1$. Then we have

$$\big(x_1 + \ldots + x_m \big) \big( y_1 + \ldots + y_n \big) = \sum_{i=1}^m \sum_{j=1}^n x_i y_j.$$

## Dedekind’s Construction of the Natural Numbers

In 1888 Richard Dedekind published the paper Was sind und was sollen die Zahlen? (What are numbers and what should they be?). In this article he gives a formal definition of finite and infinite sets and an axiomatic foundation of the natural numbers.

We will explain his brilliant ideas in this section.

Definition. Let $A$ be a set. The set $A$ is called infinite if there exists a bijective mapping $\alpha : A \rightarrow A’$ from the set $A$ onto a proper subset $A’$ of the set $A$.

Otherwise, the set $A$ is called finite.

Axiom. (Axiom of Dedkind) There exists at least one infinite set.

Definition. Let $A$ be a set, and let $\varphi : A \rightarrow A$ be a mapping from the set $A$ into itself. A subset $K$ of the set $A$ is called a chain with respect to the mapping $\varphi : A \rightarrow A$ if we have

$$\varphi(K) \subseteq K.$$

If no confusion may arise, we also speak of a chain instead of a chain with respect to the mapping $\varphi : A \rightarrow A$.

Definition. Let $S$ be a set, let $\varphi : S \rightarrow S$ be a mapping from the set $S$ into itself, and let $A$ be a subset of the set $S$.

The set

$$\bar{A} := \bigcap \: \{ K \subseteq S \mid K \mbox{ is a chain and } A \subseteq K \}$$

is called the chain generated by the set $A$.

Theorem. Let $S$ be an infinite set, let $\varphi : S \rightarrow S’$ be a bijective mapping from the set $S$ onto a proper subset $S’$ of the set $S$, let $a$ be an element of the set $S \setminus S’$, and let $N := \overline{ \{ a \} }$ be the chain generated by the set $\{ a \}$.

(a) The mapping $\varphi : S \rightarrow S’$ induces an injective mapping $\alpha : N \rightarrow N$ from the set $N$ into itself.

(b) Set $0 := a$ and

$$x^+ := \alpha(x) \mbox{ for all } x \in N.$$

Then the set $N$ is a Peano set.

## Notes and References

A list of textbooks about set theory is contained in Unit Literature about Set Theory.

A list of textbooks about numbers is contained in Unit Literature about Numbers.

Do you want to learn more? The next walk after the walk The Axioms of Zermelo and Fraenkel is the walk The Cardinality of Sets [in preparation]. Its first unit is the Unit Finite Sets and their Cardinalities [in preparation].

Within the walk Numbers [in preparation] the next unit is the Unit The Integers [in preparation].