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

Please note that the text on this web page gives a summary of the Unit The Natural Numbers and the Principle of Induction. A full text including the proofs is available as a separate pdf-document at the end of this page.

The Definition of the Natural Numbers:

What are the characteristic properties of the natural numbers which may serve as a basis for their formal definition? Peano [Peano-1889] gave in 1889 the following answer:

A set $A$ has the characteristic properties of the set $\mathbb{N}_0$ of the natural numbers if it fulfills the following conditions:

(P1) The set $A$ contains the number $0$. The number $0$ can be understood as the starting point for the definition of the natural numbers.

(P2) Starting with the number $0$ Peano defines a successor $1 = 0^+$, then a successor $2 = 1^+$ and so on. More formally, he requires the existence of a function $+ : A \rightarrow A; \: x \mapsto x^+$ from the set $A$ into itself. For a natural number $n$ the successor $n^+$ has the meaning $n^+ = n + 1$.

(P3) We want that $n+1 \neq 0$ for all natural numbers $n$. More formally, we require that $x^+ \neq 0$ for all elements $x$ of the set $A$.

(P4) We want that the mapping

$$
+ : A \rightarrow A, \: + : x \mapsto x^+ (= x + 1)
$$

is injective. In other words: If $x$ and $y$ are two elements of the set $A$ such that $x^+ = y^+$, then we have $x = y$.

Note that Axioms (P1) to (P4) are not sufficient to guarantee that the mapping $+ : A \rightarrow A \setminus \{ 0 \} $ is surjective. As an example we consider the set

$$
A := \mathbb{N}_0 \cup \{ (n, 1) \mid n \in \mathbb{N}_0 \}
$$

with

$$
n^+ := n + 1 \mbox{ and } (n, 1)^+ := (n + 1, 1) \mbox{ for all } n \in \mathbb{N}_0.
$$

It fulfills the axioms (P1) to (P4), but the element $(0, 1)$ does not have a predecessor, that is, there is no element $x \in A$ such that $x^+ = (0, 1)$. Peano solves this problem with an additional axiom (P5) as follows:

(P5) If $B$ is a subset of the set $A$ such that

$$
0 \in B \mbox{ and } x^+ \in B \mbox{ for all } x \in B,
$$

then we have $B = A$.

This axiom has the additional advantage that it provides the basis for the principle of induction.

The axioms (P1) to (P5) are called the axioms of Peano, and we have shown in Unit Successor Sets and the Axioms of Peano that there exists exactly one set $\omega$ fulfilling the axioms of Peano and additionally the conditions

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

See Theorem [#nst-th-minimal-successor-set-axiom-peano]. The set $\omega$ is called the minimal successor set.

The formal definition of the set $\mathbb{N}_0$ of the natural numbers is now very easy: We just set

$$
\mathbb{N}_0 := \omega; \: 0 := \emptyset \mbox{ and } n + 1 := n^+ := n \cup \{n \} \mbox{ for all } n \in \mathbb{N}_0 = \omega.
$$

See Definition [#nst-def-natural-numbers] and Definition [#nst-def-natural-number].

In Theorem [#nst-th-nz-peano] we shall see that the mapping $\mathbb{N}_0 \rightarrow \mathbb{N}_0 \setminus \{ 0 \} = \mathbb{N}$, $n \mapsto n+1$ is indeed bijective.

The Principle of Induction and the Recursive Definition of Functions:

The principle of induction states that if an assertion $A_0$ is true and if we may deduce the assertion $A_{n+1}$ from the assertion $A_n$ for all natural numbers $n$, then the assertion $A_n$ is true for all natural numbers $n$. Originally, this principle has been considered as a general proof technique. In the context of the axiomatics of Zermelo and Fraenkel it is just a theorem which is an immediate consequence of Axiom (P5) of Peano (see Theorem [#nst-th-principle-induction]).

Closely related to the principle of induction is the possibility to define a function $\alpha : \mathbb{N}_0 \rightarrow X$ from the set of the natural numbers into a set $X$ recursively. For example, we will define the exponentiation $a^n$ recursively by

$$
a^0 := 1 \mbox{ and } a^{n+1} := a^n \cdot a.
$$

In other words, we have to construct a function $\alpha : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ with the properties that

$$
\alpha(0) = 1 \mbox{ and } \alpha(n+1) = \alpha(n) \cdot a.
$$

Then we may define $a^n := \alpha(n)$. The formal procedure is as follows: We first define an auxiliary function $f : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ by $f : n \mapsto n \cdot a$. Then Theorem [#nst-th-minimal-successor-set-recursive-definition] guarantees the existence and the uniqueness of a function $\alpha : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ such that

$$
\alpha(0) = 1 \mbox{ and } \alpha(n+1) = f \big( \alpha(n) \big) = \alpha(n) \cdot a \mbox{ for all } n \in \mathbb{N}_0.
$$

In some cases this procedure has to be extended a little bit. Examples are discussed in Section Factorial of n and the Fibonacci Numbers.

The Addition of Natural Numbers:

A crucial property of the natural numbers is the possibility to add natural numbers. The sum $m + n$ is defined recursively. The basic properties of addition are that addition is associative (Theorem [#nst-th-natural-numbers-addition-associative]), that addition is commutative (Theorem [#nst-th-natural-numbers-addition-commutative]) and that the so-called cancellation rules hold (Theorem [#nst-th-natural-numbers-addition-cancellation-law]).

It is remarkable that the axiomatics of Zermelo and Fraenkel provides a possibility to prove these properties. Before that, one just had to accept these properties.

One way to define the natural order $0 < 1 < 2 < \ldots < n < n+1 < \ldots$ on the set of the natural numbers is based on the following property of the natural numbers: We will see in Theorem [#nst-th-natural-numbers-lemma-order] that given two natural numbers $m$ and $n$ 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$.

Case (ii) means $m < n$. Case (iii) means $n < m$. We will explain this in detail in Section The Standard Order on the Natural Numbers.

The Multiplication of Natural Numbers:

A further crucial property of the natural numbers is the possibility to multiply natural numbers. The product $m \cdot n$ is defined recursively. The basic properties of multiplication are that multiplication is associative (Theorem [#nst-th-natural-numbers-multiplication-associative]), that multiplication is commutative (Theorem [#nst-th-natural-numbers-multiplication-commutative]) and that the so-called cancellation rules hold (Theorem [#nst-th-natural-numbers-multiplication-cancellation-laws]).

The combination of addition and multiplication is expressed by the distributive laws (see Theorem [#nst-th-natural-numbers-distributive-laws]).

The Power of Natural Numbers:

Finally, we consider the power of natural numbers. The power $m^n$ is defined recursively. The basic properties of exponentiation are

$$
(km)^n = k^n \cdot m^n, \: k^{m+n} = k^m \cdot k^n \mbox{ and } (k^m)^n = k^{mn} \mbox{ for all } k, m, n \in \mathbb{N}_0.
$$

See Theorem [#nst-th-natural-numbers-k-exp-m-plus-n].

Factorial of $n$ and the Fibonacci Numbers:

The factorial $n!$ of a natural number $n$ and the Fibonacci numbers $F_n$ are two further examples of recursively defined functions. They are defined as follows:

$$
n! := 1 \cdot 2 \cdot \ldots \cdot n, \mbox{ or, equivalently, } 0! := 1 \mbox{ and } (n+1)! := n! \cdot (n+1) \mbox{ for all } n \in \mathbb{N}_0.
$$

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

Even though their definition also relies on Theorem [#nst-th-minimal-successor-set-recursive-definition], the process is a little bit more complicated. We will explain this in Example [#nst-ex-factorial] and Example [#nst-ex-fibonacci].

The Standard Order on the Natural Numbers:

Given two natural numbers $m$ and $n$ we need a method to decide whether $m = n$, $m < n$ or $m > n$ with respect to the natural order $0 < 1 < 2 < \ldots n < n+1 < \ldots $. More precisely, we need a formal definition for this order. One approach is the observation that if $m > n$, then there exists a natural number $k \neq 0$ such that $m = n + k$, for example $5 = 3 + 2$. Given two natural numbers $m$ and $n$ according to Theorem [#nst-th-natural-numbers-lemma-order] exactly one of the following possibilities occurs:

EquationMeaning
$m = n$$m = n$
$n = m + k$, $k \neq 0$$m < n$
$m = n + k$, $k \neq 0$$m > n$

Hence, one may define $m \leq n$ if there exists a natural number $k$ such that $n = m + k$ (see Definition [#nst-def-order-on-natural-numbers]). A first important conclusion is the fact that the pair $(\mathbb{N}_0, \leq)$ is a totally ordered set (see Theorem [#nst-th-order-on-natural-numbers]).

The definition of the natural order on the set of the natural numbers allows us to define the set

$$
\{0, 1, \ldots, n \} := \{x \in \mathbb{N}_0 \mid 0 \leq x \leq n \} \mbox{ for all } n \in \mathbb{N}_0.
$$

Each natural number is a the the same time a set. We recall that

$$
0 = \emptyset, \: 1 = \{ 0 \}, \: 2 = \{ 0, 1 \}, \ldots
$$

The above notation allows us to give the following concise description of the set $n$: We have

$$
0 = \emptyset \mbox{ and } n +1 = \{ 0, 1, \ldots, n \} \mbox{ for all } n \in \mathbb{N}_0.
$$

See Theorem [#nst-th-n-plus-1-equals-0-ldots-n]. The order relation on the set $\mathbb{N}_0$ can also be expressed as follows:

$$
m \leq n \mbox{ if and only if } m \subseteq n \mbox{ for all } m, n \in \mathbb{N}_0.
$$

See Theorem [#nst-th-nz-char-m-smaller-n] and Remark [#nst-rem-nz-char-m-smaller-n].

The next task is to explore the relation between the (natural) order on the set $\mathbb{N}_0$ and the algebraic operations addition, multiplication and exponentiation. The most important results are as follows: Let $a$, $b$, $c$, $d$, $m$, $n$ and $x$ be natural numbers. Then we have

\begin{eqnarray*}
a \leq c \mbox{ and } b \leq d & \Rightarrow & a + b \leq c + d \\
x + m \leq x + n & \Rightarrow & m \leq n \\
a \leq c \mbox{ and } b \leq d & \Rightarrow & ab \leq cd \\
x \neq 0 \mbox{ and } xm \leq xn & \Rightarrow & m \leq n \\
x \leq y & \Rightarrow & x^n \leq y^n \\
x \neq 0 \mbox{ and } m \leq n & \Rightarrow & x^m \leq x^n \\
n \neq 0 \mbox{ and } x^n \leq y^n & \Rightarrow & x \leq y \\
x \neq 0, \: x \neq 1 \mbox{ and } x^m \leq x^n & \Rightarrow & m \leq n
\end{eqnarray*}

Generalized Arithmetical Laws:

The additive associative law

$$
(a + b) + c = a + (b + c)
$$

allows us to write $a + b+ c$ instead of $(a + b) + c$ or $a + (b + c)$. The sum $\sum_{j=1}^n x_j$ ($x_1, \ldots, x_n \in \mathbb{N}_0$) is defined recursively by

$$
\sum_{j=1}^1 x_j := x_1 \mbox{ and } \sum_{j=1}^{n+1} x_j := \big( \sum_{j=1}^n x_j \big) + x_{n+1}.
$$

This means that

$$
\sum_{j=1}^n x_j = \big( \big( ( x_1 + x_2) + x_3 \big) + \ldots + x_n \big).
$$

The generalized associative law (see Proposition [#nst-prop-natural-numbers-generalized-associative-law]) allows us to omit all these brackets and to write

$$
\sum_{j=1}^n x_j = x_1 + \ldots + x_n.
$$

The same is true for the multiplication (see Proposition [#nst-prop-natural-numbers-generalized-associative-law]). In a similar way the generalized commutative law (see Proposition [#nst-prop-natural-numbers-generalized-commutative-law]) and the generalized distributive laws (see Proposition [#nst-prop-natural-numbers-generalized-distributive-law]) generalize the commutative law $x + y = y + x$ and the distributive laws $x (y + z) = xy + xz$ and $(x + y)z = xz + yz$.

Dedekind’s Construction of the Natural Numbers:

Richard Dedekind was the first to give an axiomatic definition of the natural numbers (see [Dedekind-1888]). Peano’s work and the axioms of Peano are based on this work of Dedekind. In the present unit we did not follow the approach of Dedekind, but introduced the set of the natural numbers as the minimal successor set defined in Unit Successor Sets and the Axioms of Peano.

In the Section Dedekind’s Construction of the Natural Numbers we will explain the brilliant approach of Dedekind.

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.

Peano Sets:

Definition. Let $A$ be a set.

(a) The set $A$ fulfills the axioms of Peano if it fulfills the following conditions:

(P1) The set $A$ contains a distinguished element $0$. In particular, the set $A$ is not empty.

(P2) There exists a function $^+ : A \rightarrow A$, $x \mapsto x^+$ from the set $A$ into itself.

(P3) We have $x^+ \neq 0$ for all elements $x$ of the set $A$.

(P4) If $x$ and $y$ are two elements of the set $A$ such that $x^+ = y^+$, then we have $x = y$, that is, the function $^+ : A \rightarrow A$ is injective.

(P5) If $B$ is a subset of the set $A$ such that

$$
0 \in B \mbox{ and } x^+ \in B \mbox{ for all } x \in B,
$$

then we have $B = A$.

(b) Let $A$ be a set fulfilling the axioms of Peano. Then the set $A$ is called a Peano set.

Theorem. There exists exactly one Peano set $\omega$ such that

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

Definition of the Natural Numbers:

Definition. Let $\omega$ be 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.

Main Properties of the Natural Numbers:

We summarize the previous results in the following theorem:

Theorem. (a) The set $\mathbb{N}_0$ contains the element $0 := \emptyset$.

(b) For each natural number $n$, the set $n + 1 := n \cup \{ n \}$ is a natural number.

(c) We have $n +1 \neq 0$ for all natural numbers $n$.

(d) Let $n$ and $m$ be two natural numbers such that $n + 1 = m + 1$. Then we have $n = m$.

(e) Let $M$ be a subset of the set $\mathbb{N}_0$ such that

$$
0 \in M \mbox{ and } m + 1 \in M \mbox{ for all } m \in M.
$$

Then we have $M = \mathbb{N}_0$.

(f) Let $M$ be a subset of the set $\mathbb{N}$ such that

$$
0 \notin M, 1 \in M \mbox{ and } m + 1 \in M \mbox{ for all } m \in M.
$$

Then we have $M = \mathbb{N}$.

(g) Let $n$ be a natural number. If $n \neq 0$, then there exists a natural number $k$ such that $n = k + 1$.

(h) The mapping $\alpha : \mathbb{N}_0 \rightarrow \mathbb{N}, \: n \mapsto n + 1$ is bijective.

For the proof of Proposition [#nst-prop-m-subset-n-plus-1] we need the following property of transitive sets which is explained in detail in Unit Successor Sets and the Axioms of Peano.

Definition. A set $A$ is called a transitive set if every element of the set $A$ is at the same time a subset of the set $A$.

Proposition. (a) The set $\mathbb{N}_0$ of the natural numbers is a transitive set.

(b) Each natural number $n$ is a transitive set.

Proposition. Let $m$ and $n$ be two natural numbers such that the set $m$ is a subset of the set $n + 1$. Then we have

$$
m \subseteq n \mbox{ or } m = n + 1.
$$

Historical Notes:

Historical notes can be found at the end of Section Dedekind’s Construction of the Natural Numbers.

The Principle of Induction and the Recurisive Definition of Functions

The Principle of Induction:

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.

Recursive Definition of Functions:

We will base the possibility of the recursive definition of a function $\alpha : \mathbb{N}_0 \rightarrow X$ from the set $\mathbb{N}_0$ of the natural numbers into a set $X$ (Theorem [#nst-th-natural-numbers-recursion-theorem]) on the corresponding result for the minimal successor set $\omega$ explained in Unit Successor Sets and the Axioms of Peano:

Theorem. (Recursive Definition) 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 : \omega \rightarrow X$ from the minimal successor set $\omega$ into the set $X$ fulfilling the following conditions:

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

(ii) We have $\alpha(A^+) = f( \alpha(A) )$ for each element $A$ of the set $\omega$.

Since $\mathbb{N}_0 = \omega$, we may reformulate the recursive definition of functions (Theorem [#nst-th-minimal-successor-set-recursive-definition]) for natural numbers as follows:

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

Definition of 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.

Remark. The definition of the addition of natural numbers relies on the consideration that

$$
m + n = m + \underbrace{1 + \ldots + 1}_{n \mbox{ times}}.
$$

An alternative way to define the addition of two natural numbers $m$ and $n$ is to choose two disjoint sets $A$ and $B$ with $|A| = m$ and $|B| = n$ elements and to define

$$
m + n := |A \mathbin{\dot{\cup}} B|.
$$

This approach is explained in Unit [Cardinal Arithmetics – in preparation].

Addition is Associative:

Proposition. (a) We have

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

(b) We have

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

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}

Addition is Commutative:

Proposition. (a) We have

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

(b) We have

\begin{equation}
(m + 1) + n = (m + n) + 1 \mbox{ for all } 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}

The Additive Cancellation Laws:

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

Definition of 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.

Remark. The definition of the multiplication of natural numbers in Definition [#nst-def-multiplication-recursion] relies on the consideration that

$$
mn = \underbrace{m + \ldots + m}_{n \mbox{ times}}.
$$

An alternative way to define the multiplication of two natural numbers $m$ and $n$ is to choose two sets $A$ and $B$ with $|A| = m$ and $|B| = n$ elements and to define

$$
m \cdot n := |A \times B|.
$$

This approach is explained in Unit [Cardinal Arithmetics – in preparation].

Elementary Properties of the Multiplication:

Proposition. (a) We have

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

(b) We have

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

(c) We have

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

Proposition. We have

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

Multiplication is Associative:

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}

Proposition. (a) We have

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

(b) We have

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

Multiplication is Commutative:

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}

The Distributive Laws:

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}

The Multiplicative Cancellation Laws:

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

Definition of the $n$th power:

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

Remark. The definition of the exponentiation of natural numbers in Definition [#nst-def-power-recursion] relies on the consideration that

$$
m^n = \underbrace{m \cdot \ldots \cdot m}_{n \mbox{ times}}.
$$

An alternative way to define the exponentiation $m^n$ for two natural numbers $m$ and $n$ is to choose two sets $A$ and $B$ with $|A| = m$ and $|B| = n$ elements and to define

$$
m^n := | \{ \alpha : B \rightarrow A \mid \alpha \mbox{ is a function from the set $B$ into the set $A$} \} |.
$$

This approach is explained in Unit [Cardinal Arithmetics – in preparation].

Elementary Properties of the $n$th power:

Proposition. (a) We have

\begin{equation}
m^0 = 1 \mbox{ for all } m \in \mathbb{N}_0.
\end{equation}

(b) We have

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

(c) We have

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

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

Remark. Note that it will follow from Proposition [#nst-prop-nz-exponentiation-2] that the equation $x^n = y^n$ implies that $n = 0$ or $x = y$.

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

or, equivalently, by

$$
0! := 1, \: (n+1)! := n! (n+1) \mbox{ for all } n \in \mathbb{N}.
$$

Hence, we have to construct a function $\beta : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ with the property that

$$
\beta(0) = 1 \mbox{ and } \beta(n+1) = \beta(n) \cdot (n+1) \mbox{ for all } n \in \mathbb{N}_0.
$$

The idea is to construct a function $\alpha : \mathbb{N}_0 \rightarrow \mathbb{N}_0 \times \mathbb{N}_0$ such that

$$
\alpha(n) = ( n!, n + 1) \mbox{ for all } n \in \mathbb{N}_0
$$

and to define the function $\beta : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ by $ \beta := {\rm pr}_1 \circ \alpha$ where

$$
{\rm pr}_1 : \mathbb{N}_0 \times \mathbb{N}_0 \rightarrow \mathbb{N}_0, \: {\rm pr}_1 : (x, y) \mapsto x
$$

denotes the projection on the first component (for more details about projections see Unit Families and the Axiom of Choice).

For, let $f : \mathbb{N}_0 \times \mathbb{N}_0 \rightarrow \mathbb{N}_0 \times \mathbb{N}_0$ be the function defined by

$$
f(m, n) := (m n, m + 1) \mbox{ for all } m, n \in \mathbb{N}_0.
$$

By Theorem [#nst-th-natural-numbers-recursion-theorem], there exists a function $\alpha : \mathbb{N}_0 \rightarrow \mathbb{N}_0 \times \mathbb{N}_0$ such that

$$
\alpha(0) = (1, 1) \mbox{ and } \alpha(n+1) = f \big( \alpha(n) \big) \mbox{ for all } n \in \mathbb{N}_0.
$$

Let $\beta : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ be defined by $\beta := {\rm pr}_1 \circ \alpha$. As indicated above we have to verify that

$$
\beta(0) = 1 \mbox{ and } \beta(n+1) = \beta(n) \cdot (n+1) \mbox{ for all } n \in \mathbb{N}_0.
$$

For, we will show by induction on $n$ that

$$
\beta(0) =1, \: \alpha(n) = \big(\beta(n), n+1\big) \mbox{ and } \beta(n+1) = \beta(n) \cdot (n + 1) \mbox{ for all } n \in \mathbb{N}_0.
$$

$n = 0$: We have $\alpha(0) = (1, 1)$ implying that $\beta(0) = {\rm pr}_1 \big(\alpha(0) \big) = 1$. In particular, we have

$$
\alpha(0) = (1, 1) = \big(\beta(0), 0 + 1\big).
$$

$n \mapsto n + 1$: By induction, we have

$$
\alpha(n+1) = f \big(\alpha(n) \big) = f \big( \beta(n), n+1 \big) = \big( \beta(n) (n+1), n+2 \big)
$$

implying that $\beta(n+1) = {\rm pr}_1 \big( \alpha(n+1) \big) = \beta(n) (n+1)$. In particular, we have

$$
\alpha(n+1) = \big( \beta(n) (n+1), n+2 \big) = \big( \beta(n+1), (n+1)+1 \big).
$$

The uniqueness of the function $\beta : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ follows by induction.

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

Hence, we have to construct a function $\beta : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ with the property that

$$
\beta(0) = 1, \: \beta(1) = 1 \mbox{ and } \beta(n+2) = \beta(n+1) + \beta(n) \mbox{ for all } n \in \mathbb{N}_0.
$$

The idea is to construct a function $\alpha : \mathbb{N}_0 \rightarrow \mathbb{N}_0 \times \mathbb{N}_0$ such that

$$
\alpha(0) = (1, 0) \mbox{ and } \alpha(n + 1) = ( F_{n+1}, F_n) \mbox{ for all } n \in \mathbb{N}_0
$$

and to define the function $\beta : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ by $ \beta := {\rm pr}_1 \circ \alpha$ where

$$
{\rm pr}_1 : \mathbb{N}_0 \times \mathbb{N}_0 \rightarrow \mathbb{N}_0, \: {\rm pr}_1 : (x, y) \mapsto x
$$

denotes the projection on the first component as in Example [#nst-ex-factorial].

For, let $f : \mathbb{N}_0 \times \mathbb{N}_0 \rightarrow \mathbb{N}_0 \times \mathbb{N}_0$ be the function defined by

$$
f(m, n) := (m + n, m) \mbox{ for all } m, n \in \mathbb{N}_0.
$$

By Theorem [#nst-th-natural-numbers-recursion-theorem], there exists a function $\alpha : \mathbb{N}_0 \rightarrow \mathbb{N}_0 \times \mathbb{N}_0$ such that

$$
\alpha(0) = (1, 0) \mbox{ and } \alpha(n+1) = f \big( \alpha(n) \big) \mbox{ for all } n \in \mathbb{N}_0.
$$

Let $\beta : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ be defined by $\beta := {\rm pr}_1 \circ \alpha$. As indicated above we have to verify that

$$
\beta(0) = 1, \: \beta(1) = 1 \mbox{ and } \beta(n+2) = \beta(n+1) + \beta(n) \mbox{ for all } n \in \mathbb{N}_0.
$$

For, we will show by induction on $n$ that $\alpha(0) = (1, 0), \: \alpha(1) = (1, 1), \: \beta(0) = 1, \: \beta(1) = 1$ and

\begin{eqnarray*}
\alpha(n+2) & = & \big( \beta(n+2), \beta(n+1) \big) \mbox{ and } \\
\beta(n+2) & = & \beta(n+1) + \beta(n) \mbox{ for all } n \in \mathbb{N}_0.
\end{eqnarray*}

$n = 0$: We have $\alpha(0) = (1, 0)$ implying that $\beta(0) = {\rm pr}_1 \big(\alpha(0) \big) = 1$.

$n=1$: We have

$$
\alpha(1) = f \big( \alpha(0) \big) = f(1, 0) = (1, 1)
$$

implying that $\beta(1) = {\rm pr}_1 \big(\alpha(1) \big) = 1$.

In particular, we have

$$
\alpha(1) = (1, 1) = \big( \beta(1), \beta(0) \big).
$$

$n+1 \mapsto n + 2$: By induction, we have

$$
\alpha(n+2) = f \big(\alpha(n+1) \big) = f \big( \beta(n+1), \beta(n) \big) = \big( \beta(n+1) + \beta(n), \beta(n+1) \big)
$$

implying that $\beta(n+2) = {\rm pr}_1 \big( \alpha(n+2) \big) = \beta(n+1) + \beta(n)$. In particular, we have

$$
\alpha(n+2) = \big( \beta(n+1) + \beta(n), \beta(n+1) \big) = \big( \beta(n+2), \beta(n+1) \big).
$$

The uniqueness of the function $\beta : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ follows by induction.

The Standard Order on the Natural Numbers

Definition of the Standard Order on the Set $\mathbb{N}_0$:

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 (Definition [#nst-def-order-on-natural-numbers]).

Proposition. Let $m$ and $n$ be two natural numbers. Then the following two conditions are equivalent:

(i) We have $m < n$.

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

Elementary Properties of the Ordered Set $\mathbb{N}_0$:

Proposition. Let $m$ and $n$ be two natural numbers.

(a) If $n \neq 0$, then we have $0 < n$.

(b) We have $n < n +1$.

(c) We have $m \leq n$ if and only if $m + 1 \leq n + 1$.

(d) We have $m < n$ if and only if $m + 1 < n + 1$.

(e) If $m < n$, then we have $m + 1 \leq n$.

(f) If $m < n +1$, then we have $m \leq n$.

(g) If $m < n \leq m + 1$, then we have $n = m + 1$.

Theorem. Let $m$ and $n$ be two natural numbers.

(a) We have $m \subseteq n$ if and only if $m \leq n$.

(b) We have $m \subset n$ if and only if $m < n$.

Remark. Theorem [#nst-th-nz-char-m-smaller-n] can also be used for an alternative definition of the standard order on the natural numbers as follows: For two natural numbers $m$ and $n$, we define

$$
m \leq n \mbox{ if and only if } m \subseteq n.
$$

Theorem. Let $n$ be a natural number. Then we have $n = \{ x \in \mathbb{N}_0 \mid x < n \}$.

Definition. Let $m$ and $n$ be two natural numbers. We set

$$
\{m, m +1, \ldots, n \} := \left\{
\begin{array}{lll}
\{ x \in \mathbb{N}_0 \mid m \leq x \mbox{ and } x \leq n \} & \mbox{ if } & m \leq n \mbox{ and} \\
\emptyset & \mbox{ if } & m > n.
\end{array}
\right.
$$

Note that $\{n, n +1, \ldots, n \} = \{ n \}$.

Theorem. Let $n$ be a natural number. Then we have

$$
n + 1 = \{ 0, 1, \ldots, n \}.
$$

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.

Addition and Order:

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

Multiplication and Order:

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

Exponentiation and Order:

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

Isomorphism between $\mathbb{N}_0$ and $\mathbb{N}$:

We recall the definition of an isomorphism of ordered sets introduced in Unit Ordered Sets and the Lemma of Zorn:

Definition. Let $A = (A, \leq_A)$ and $B = (B, \leq_B)$ be two ordered sets. A bijective mapping $\alpha : A \rightarrow B$ is called an isomorphism from the ordered set $A$ onto the ordered set $B$ if we have

$$
x \leq_A y \mbox{ if and only if } \alpha(x) \leq_B \alpha(y) \mbox{ for all } x, y \in A.
$$

Proposition. The function $\alpha : \mathbb{N}_0 \rightarrow \mathbb{N}$, $\alpha : n \mapsto n + 1$ is an isomorphism form the ordered set $(\mathbb{N}_0, \leq)$ onto the ordered set $(\mathbb{N}, \leq)$. In particular, the sets $(\mathbb{N}_0, \leq)$ and $(\mathbb{N}, \leq)$ are isomorphic.

Generalized Arithmetic Laws

Sums and Products:

Definition. Let $m$ and $n$ be two natural numbers, let $I := \{m , m + 1, \ldots, n\}$ (Definition [#nst-def-n-ldots-m]), 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\}$ (Definition [#nst-def-n-ldots-m]), 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.
$$

Generalized Associative Law:

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

Generalized Commutative Law:

Proposition. Let $y$ be a natural number, and let $x_1, \ldots, x_n$ be a sequence of natural numbers for some natural number $n \geq 1$.

(a) We have

$$
y + x_1 + \ldots + x_n = x_1 + \ldots + x_n + y.
$$

(b) We have

$$
y \cdot x_1 \cdot \ldots \cdot x_n = x_1 \cdot \ldots \cdot x_n \cdot y.
$$

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

Generalized Distributive Law:

Proposition. Let $x$ be a natural number, and let $y_1, \ldots, y_n$ be a sequence of natural numbers for some natural number $n \geq 1$. Then we have

$$
\sum_{j=1}^n (x y_j) = x \big( \sum_{j=1}^n y_j \Big) = \big( \sum_{j=1}^n y_j \Big) x.
$$

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

Richard Dedekind published in 1872 the paper Stetigkeit und irrationale Zahlen (Continuity and irrational numbers) [Dedekind-1872] where he gave an axiomatic foundation of the real numbers based on what is today called the cuts of Dedekind. For more details see Unit [The Real Numbers – in preparation].

In 1888 he published the paper Was sind und was sollen die Zahlen? (What are numbers and what should they be?) [Dedekind-1888]. 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. The ideas of Dedekind are based on his definition of a chain. We start by explaining chains in the context of the natural numbers:

Chains in the Set $\mathbb{N}_0$:

Definition. Let $k$ be a natural number. The set

$$
T_k := \{ x \in \mathbb{N}_0 \mid x \geq k \}
$$

is called a chain or a Dedekind chain in the set $\mathbb{N}_0$. In addition, the set $T_{\infty} := \emptyset$ is called the empty chain.

Proposition. Let $\varphi : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ be defined by $\varphi(n) := n+1$ for all natural numbers $n$, and let $A$ be a subset of the set $\mathbb{N}_0$.

Then the set $A$ is a chain in the set $\mathbb{N}_0$ if and only if

$$
\varphi(A) \subseteq A.
$$

Proposition. Let $\big( K_i \big)_{i \in I}$ be a family of chains in the set $\mathbb{N}_0$. Then the set $\bigcap_{i \in I} K_i$ is also a chain in the set $\mathbb{N}_0$.

Definition. Let $A$ be a subset of the set $\mathbb{N}_0$, and let

$$
\bar{A} := \bigcap \: \{ K \subseteq \mathbb{N}_0 \mid K \mbox{ is a chain and } A \subseteq K \}.
$$

The set $\bar{A}$ is called the chain in the set $\mathbb{N}_0$ generated by the set $A$.

Proposition. Let $A$ be a subset of the set $\mathbb{N}_0$, and let $\bar{A}$ be the chain in the set $\mathbb{N}_0$ generated by the set $A$.

(a) If $A = \emptyset$, then we have $\bar{A} = A = \emptyset$.

(b) If $A \neq \emptyset$ and if $k$ is the minimal element of the set $A$, then we have

$$
\bar{A} = T_k = \{ x \in \mathbb{N}_0 \mid x \geq k \}.
$$

(c) Let $a$ be a natural number. Then we have

$$
\overline{ \{a\} } = T_a = \{ x \in \mathbb{N}_0 \mid x \geq a \}.
$$

Proposition. Let $A := \{ 0 \}$, and let $\varphi : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ be defined by $\varphi(n) := n + 1$ for all natural numbers $n$. Then we have $\bar{A} = \mathbb{N}_0$ and $\varphi(\bar{A})= \mathbb{N}$.

Dedekind’s Construction of the Natural Numbers:

Dedekind’s idea is as follows. He starts with the definition that a 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$. As a next step he postulates the existence of infinite sets (see Definition [#nst-def-infinity-Dedekind] and Axiom[#nst-def-axiom-infinity-Dedekind]).

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. There exists at least one infinite set.

His next observation is that each infinite set contains a set “similar” to the set of the natural numbers. Today we would say that each infinite set contains a Peano set. In Proposition [#nst-prop-generated-chain-0] we have seen the following:

Let $A := \{ 0 \}$, and let $\varphi : \mathbb{N}_0 \rightarrow \mathbb{N}_0$ be defined by $\varphi(n) := n + 1$ for all natural numbers $n$. Then we have $\bar{A} = \mathbb{N}_0$ and $\varphi(\bar{A})= \mathbb{N}$.

Dedekind is now going in the opposite direction: Given an infinite set $S$ he starts with a mapping $\varphi : S \rightarrow S$, and he looks for a subset $N$ of the set $S$ which may serve as the set of the natural numbers or, in other words, which is a Peano set. This set $N$ should fulfill the following requirements:

(i) The mapping $\varphi : S \rightarrow S$ shall induce a mapping $\alpha : N \rightarrow N$. In other words, we need that the set $\varphi(N)$ is a subset of the set $N$. Later on, we will define

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

(ii) The set $N$ contains a distinguished element $a$ such that

$$
\alpha(x) \neq a \mbox{ for all } x \in N.
$$

Later on, he will set $0 := a$.

(iii) The set $N$ is not too big, in other words, it should contain the elements

$$
0, 1 = \alpha(0), 2 = \alpha(1), \ldots,
$$

but no further elements.

Proposition [#nst-prop-generated-chain-0] motivates the following idea: Let $\varphi : S \rightarrow S$ be a mapping from the set $S$ into itself, let $a$ be an (appropriate) element of the set $S$, and let $N$ be the chain generated by the set $\{ a \}$.

To do so, we have first to generalize the concept of a chain to an arbitrary set $S$. This is done in Definition [#nst-def-chain-Dedekind]. As a next step we have to define what a chain generated by a subset is. The definition is quite obvious and is the content of Definition [#nst-def-generated-chain-Dedekind].

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

Proposition. Let $A$ be a set, let $\varphi : A \rightarrow A$ be a mapping from the set $A$ into itself, and let $\big( K_i \big)_{i \in I}$ be a (non-empty) family of chains with respect to the mapping $\varphi : A \rightarrow A$. Then the set

$$
\bigcap_{i \in I} K_i
$$

is also a chain.

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

(a) The set

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

is a chain.

(b) We have

$$
A \subseteq \bar{A} \mbox{ and } A = \bar{A} \mbox{ if and only if the set $A$ is a chain.}
$$

(c) Let $B$ be a chain containing the set $A$ as a subset. Then the chain $\bar{A}$ is also a subset of the set $B$.

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

defined in Proposition [#nst-prop-generated-chain] is called the chain generated by the set $A$.

The definition of a chain in Definition[#nst-def-chain-Dedekind] implies that we have

$$
\varphi(N) \subseteq N \mbox{ for } N := \overline{ \{a\} }.
$$

Hence, the mapping $\varphi : S \rightarrow S$ induces a mapping $\alpha : N \rightarrow N$. It remains to guarantee that the mapping $\alpha : N \rightarrow N$ is injective and that

$$
\alpha(x) \neq a \mbox{ for all } x \in N.
$$

The first property can easily be guaranteed if the mapping $\varphi : S \rightarrow S$ is injective. The second property can be guaranteed if there already exists an element $a$ of the set $S$ such that

$$
\varphi(x) \neq a \mbox{ for all } x \in S.
$$

To do so, Dedekind comes back to his definition of an infinite set $S$ stating that there exists a bijective mapping $\varphi : S \rightarrow S’$ from the set $S$ onto a proper subset $S’$ of the set $S$. This mapping is by definition injective, and for an element $a$ of the set $S \setminus S’$ we have

$$
\varphi(x) \neq a \mbox{ for all } x \in S.
$$

In Theorem [#nst-th-chain-Peano] we will see that this setting works quite well, that is, that the resulting set $N$ with the distinguished element $a$ is a Peano set.

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.

Historical Notes:

For the formal definition of finite and infinite sets, for the definition of the Peano sets and for the recursive definition of functions see the historical notes in Unit Successor Sets and the Axioms of Peano.

The first formal definition of the natural numbers is due to Dedekind as explained in detail above:

71. Erklärung. Ein System $N$ heißt einfach unendlich, wenn es eine solche ähnliche Abbildung $\varphi$ von $N$ in sich selbst gbt, dass $N$ als Kette […] eines Elements erscheint, welches nicht in $\varphi(N)$ enthalten ist. Wir nennen dieses Element, das wir im Folgenden durch das Symbol $1$ bezeichnen wollen, das Grundelement von $N$ und sagen zugleich, das einfach unendliche System $N$ sei durch diese Abbildung $\varphi$ geordnet.

Behalten wir die früheren bequemen Bezeichnungen für die Bilder und Ketten bei […], so besteht mithin das Wesen eines einfach uendlichen Systems $N$ in der Existenz einer Abbildung $\varphi(N)$ und eines Elements $1$, die den folgenden Bedingungen $\alpha$, $\beta$, $\gamma$ und $\delta$ genügen:

$\alpha$. $N’ \subseteq N$.

$\beta$. $N = 1_0$.

$\gamma$. Das Element $1$ ist nicht in $N’$ enthalten.

$\delta$. Die Abbildung $\varphi$ ist ähnlich.

See [Dedekind-CW], Volume 3, p. 359.

71. Explanation. A system $N$ is called simply infinite if there exists a similar mapping $\varphi$ of $N$ into itself such that $N$ is a chain of an element which is not contained in $\varphi(N)$. We call this element, which we want to denote by the symbol $1$ in the following, the basic element of $N$ and we say at the same time that the simply infinite system $N$ is ordered by this mapping $\varphi$.

If we keep the previous convenient names for the images and chains, […] the essence of a simply infinite system $N$ is the existence of a map $\varphi(N)$ and an element $1$ that fulfill the following conditions $\alpha$, $\beta$, $\gamma$ and $\delta$:

$\alpha$. $ N’ \subseteq N$.

$\beta$. $N = 1_0$.

$\gamma$. The element $1$ is not contained in $N’$.

$\delta$. The mapping $\varphi$ is similar.

(Translation by the author.)

“Similar” means injective. “$N$ is a chain of an element” means that the set $N$ is the chain generated by the set $\{a\}$ (see Definition [#nst-def-generated-chain-Dedekind]). Note that Dedekind starts his construction of the set of the natural numbers with the element $1$, whereas we started with the element $0$.

A simply infinite set is an infinite set $N$ with the property that there exists an element $a$ (called $1$) of the set $N$ and an injective mapping $\varphi : N \rightarrow N \setminus \{a\}$ such that $N = \overline{\{a\}}$.

Dedekind’s condition $(\alpha)$ ($N’ \subseteq N$) means that the set $\varphi(N)$ is a subset of the set $N$. More generally, Dedekind’s notation $X’$ means $\varphi(X)$.

Condition $(\beta)$ ($N = 1_0$) means that the set $N$ is the chain generated by the set $\{1\}$. More generally, Dedekind’s notation $X_0$ means $\bar{X}$ (see Definition [#nst-def-generated-chain-Dedekind]).

Condition $(\gamma)$ (The element $1$ is not contained in $N’$) means that $\varphi(x) \neq 0$ (or $\varphi(x) \neq 1$ if we start the natural numbers with the number $1$) for all elements $x$ of the set $N$.

Finally, Condition $(\delta)$ (The mapping $\varphi$ is similar) means that the mapping $\varphi : N \rightarrow N$ is injective.

*

As a next step Dedekind proves the principle of induction:

80. Satz der vollständigen Induktion. (Schluss von $n$ auf $n’$). Um zu beweisen, dass ein Satz für alle Zahlen $n$ einer Kette $m_0$ gilt, genügt es zu zeigen,

$\rho$. dass er für $n = m$ gilt und

$\sigma$. dass aus der Gültigkeit des Satzes für eine Zahl $n$ der Kette $m_0$ stets seine Gültigkeit auch für die folgende Zahl $n’$ folgt.

See [Dedekind-CW], Volume 3, p. 361.

80. Theorem of induction. (Deduction from $n$ to $n’$). To prove that a sentence is valid for all numbers $n$ in a chain $m_0$, it is sufficient to show

$\rho$. that it holds for $n = m$ and

$\sigma$. that the validity of the sentence for a number $n$ of the chain $m_0$ always implies its validity for the following number $n’$.

(Translation by the author.)

Note that Dedekind’s notations $m_0$ and $n’$ mean

$$
m_0 = T_m = \{ x \in \mathbb{N}_0 \mid x \geq m \} \mbox{ and } n’ = n+1.
$$

*

Dedekind also introduces the standard order on the natural numbers. As we have seen in Proposition [#nst-prop-generated-chain-n0] we have

$$
\overline{ \{a\} } = T_a = \{ x \in \mathbb{N}_0 \mid x \geq a \} \mbox{ for all } a \in \mathbb{N}_0.
$$

Since Dedekind uses the notation $a_0$ for $\overline{ \{a\} }$, he introduces the standard order on the set of the natural numbers as follows:

89. Erklärung. Die Zahl $m$ heißt kleiner als die Zahl $n$ […], wenn die Bedingung

$$
n_0 \subseteq m_0′
$$

erfüllt ist […].

See [Dedekind-CW], Volume 3, p. 363.

89. Explanation. The number $m$ is called smaller than the number $n$ […] if the condition

$$
n_0 \subseteq m_0′
$$

is satisfied […].

(Translation by the author.)

This is equivalent to say that

$$
m \leq n \mbox{ if and only if } n_0 = T_n \subseteq T_m = m_0.
$$

Note that we have

$$
\mathbb{N}_0 = \{ x \in \mathbb{N}_0 \mid x < n \} \mathbin{\dot{\cup}} \{ x \in \mathbb{N}_0 \mid x \geq n \} = n \mathbin{\dot{\cup}}  T_n.
$$

So the definition

$$
m \leq n \mbox{ if and only if } T_n \subseteq T_m
$$

is equivalent to the definition

$$
m \leq n \mbox{ if and only if } m \subseteq n.
$$

explained in Theorem [#nst-th-nz-char-m-smaller-n] and Remark [#nst-rem-nz-char-m-smaller-n]. In other words, our definition of the natural numbers is equivalent to say that

$$
n = \{x \in \mathbb{N}_0 \mid x < n \},
$$

whereas Dedekind’s definition corresponds to

$$
n = \{ x \in \mathbb{N}_0 \mid x \geq n \}.
$$

Both approaches have their specific advantages.

Finally, Dedekind also introduces the addition, the multiplication and the exponentiation of the natural numbers. All this is done quite similar to the way explained in the previous sections. In fact, all results of this unit are already contained in Dedekind’s paper of 1888.

Notes and References

A crucial step in the development of the natural numbers was the introduction of our decimal number system which has been invented about 500 AD in Northern India. Arabian mathematicians, in particular Abu Dscha’far Muhammad ibn Musa al-Chwarizmi, took up these results and spread them around the world. An excellent account about the history of number systems is the book Histoire universelle des chiffres from Georges Ifrah [Ifrah-1981] (for an English and a German translation see [Ifrah-1998-en] and [Ifrah-1989-de]).

For additional textbooks please have a look at the webpages Literature about Set Theory and Literature about Numbers.

[Dedekind-1872] Dedekind, Richard (1872). Stetigkeit und irrationale Zahlen. Braunschweig: Vieweg.

[Dedekind-1888] Dedekind, Richard (1888). Was sind und was sollen die Zahlen? Braunschweig: Vieweg.

[Dedekind-CW] Dedekind, Richard (1932). Gesammelte mathematische Werke. Ed. by Robert Fricke, Emmy Noether, and Öystein Ore. Braunschweig: Vieweg.
There are three volumes: Volume 1: (1930), Volume 2: (1931), Volume 3: (1932).

[Ifrah-1981] Ifrah, Georges (1981). Histoire Universelle des Chiffres. Paris: Editions Seghers.
For an English and a German version see [Ifrah-1998-en] and [Ifrah-1989-de].

[Ifrah-1989-de] Ifrah, Georges (1989). Universalgeschichte der Zahlen. Frankfurt, New York: Campus-Verlag.
German translation of [Ifrah-1981].

[Ifrah-1998-en] Ifrah, Georges (1998). Universal History of Numbers. London: Harville Press.
English translation of [Ifrah-1981].

[Peano-1889] Peano, Giuseppe (1889). Arithmetices Prinicipia – Nova Methodo Exposita. Romae and Florentiae: Augustae Taurinorum.
This book is published under the name Ioseph Peano.

Download

The pdf document is the full text including the proofs.

Change History

VersionDateChanges
1.0.0July 2020Creation