The Natural Numbers and the Principle of Induction

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:

• Addition of natural Numbers
• Multiplication of Natural Numbers
• Exponentiation of Natural Numbers
• Standard Order of the Natural Numbers

---

The main results are

• The Principle of Induction (Theorem [#nst-th-principle-induction])
• The Recursive Definition of Functions (Theorem [#nst-th-natural-numbers-recursion-theorem])
• The Standard Laws about the Addition and Multiplication of Natural Numbers
• The Standard Laws about the Order and the Addition and Multiplication of Natural Numbers

---

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.

---

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

---

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

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

(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.

---

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

---

---

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

---

---

The Addition of Natural Numbers

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

---

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

---

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

---

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

---

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

---

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

---

(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:

---

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

---

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

---

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

---

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

---

(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}

---

(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:

---

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

---

\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.

---

\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}

---

(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]).

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

For more details see the full text.

---

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

---

$$
n = m + r.
$$

The order $\leq$ is called the standard order on the set of the 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$.

---

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

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

---

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

---

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

---

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

---

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

---

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:

---

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

---

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

---

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

---

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

---

$$
\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)
$$

---

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

---

Otherwise, the set $A$ is called finite.

---

---

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

---

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

---

(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].

---

---

Download

The pdf document is the full text including the proofs.

Current Version: 1.0.1 from October 2020