Successor Sets and the Axioms of Peano

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 seventh unit of the walk The Axioms of Zermelo and Fraenkel. We will explain the last of the axioms of Zermelo and Fraenkel, namely the axiom of infinity. It will allows us to deduce the axioms of Peano from the axioms of Zermelo and Fraenkel. As a consequence we will be able to formally introduce the natural numbers in Unit The Natural Numbers and the Principle of Induction.


We will introduce the following axiom:


You will learn the meaning of the following terms:


The main results are



Successor Sets and the Axiom of Infinity

In this section we will explain the concept of successor sets and the axiom of infinity. We will see that the axiom of infinity guarantees the existence of successor sets.


Definition. Let $A$ be a set. Then the set $A^+ := A \cup \{ A \}$ is called the successor of the set $A$.

French / German. Successor = Successeur = Nachfolger.


Axiom. (ZFC-10: Axiom of Infinity) There exists a set ${\cal A}$ fulfilling the following conditions:

(i) The empty set $\emptyset$ is an element of the set ${\cal A}$.

(ii) If $A$ is an element of the set ${\cal A}$, then its successor $A^+$ is also an element of the set ${\cal A}$.


Definition. Let ${\cal A}$ be a set fulfilling the following conditions:

(i) The empty set $\emptyset$ is an element of the set ${\cal A}$.

(ii) If $A$ is an element of the set ${\cal A}$, then its successor $A^+$ is also an element of the set ${\cal A}$.

Then the set ${\cal A}$ is called a successor set.

Note that the axiom of infinity guarantees that there exists at least one successor set.



The Minimal Successor Set

In this section we will explain what the minimal successor set $\omega$ is. In Unit Natural Numbers and the Principle of Induction we will set $\mathbb{N}_0 := \omega$, that is, we will define that the set of the natural numbers is the minimal successor set $\omega$. In addition, we will set $n + 1 := n^+$.


Definition. Let $\omega$ be the successor set with the following property: If ${\cal S}$ is a successor set, then the set $\omega$ is a subset of the set ${\cal S}$ (Theorem [#nst-th-existence-omega]).

The successor set $\omega$ is called the minimal successor set. It is denoted by $\omega$.


Theorem. There exists exactly one successor set $\omega$.


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

French / German. Transitive set = Ensemble transitif = Transitive Menge.


Proposition. Let $\omega$ be the minimal successor set.

(a) The minimal successor set $\omega$ is a transitive set.

(b) Let $A$ be an element of the set $\omega$. Then the set $A$ is a transitive set.



The Axioms of Peano

Giuseppe Peano introduced the axioms of Peano as an axiomatic system for the definition of natural numbers. We will explain the concept of the axioms of Peano and show that the minimal successor set is a Peano set:


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.

French / German. Peano set = Ensemble de Peano = Peano-Menge.


Theorem. The minimal successor set $\omega$ is a Peano set where $0 := \emptyset$ and $A^+ := A \cup \{A\}$ for all elements $A$ of the set $\omega$.



The Recursion Theorem

The recursion theorem allows the recursive definition of functions.


Theorem. (Recursion Theorem) 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$.

French / German. Recursion theorem = Thórème de récursivité = Rekursionssatz.



Isomorphisms of Peano Sets

In this section we will explain the isomorphisms between Peano sets. The main result ist Theorem [#nst-th-axiom-peano-bijection] saying that any two Peano sets are isomorphic.


Definition. Let $A$ and $B$ be two Peano sets.

(a) A function $\alpha : A \rightarrow B$ is called an isomorphism from the Peano set $A$ onto the Peano set $B$ if the following conditions are fulfilled:

(i) The function $\alpha : A \rightarrow B$ is bijective. Let $\beta := \alpha^{-1} : B \rightarrow A$.

(ii) We have $\alpha(0_A) = 0_B$.

(iii) We have $\alpha(x^+) = \alpha(x)^+$ for all elements $x$ of the set $A$.

(iv) We have $\beta(0_B) = 0_A$.

(v) We have $\beta(y^+) = \beta(y)^+$ for all elements $y$ of the set $B$.

(b) If $A$ and $B$ are two Peano sets such that there exists an isomorphism $\alpha: A \rightarrow B$ from the Peano set $A$ onto the Peano set $B$, then the Peano sets $A$ and $B$ are called isomorphic. In this case we write $A \cong B$.

French / German. Isomorphic Peano sets = Ensembles de Peano isomorphes = Isomorphe Peano-Mengen.


Theorem. Let $A$ and $B$ be two Peano sets.

(a) The Peano sets $A$ and $B$ are isomorphic.

(b) There exists exactly one isomorphism $\alpha : A \rightarrow B$ from the Peano set $A$ onto the Peano set $B$.



Notes and References

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


Do you want to learn more? The last unit of the walk The Axioms of Zermelo and Fraenkel shows the full strength of the concept: In Unit The Natural Numbers and the Principle of Induction we will formally introduce the set $\mathbb{N}_0$ of the natural numbers in the framework of Zermelo and Fraenkel.



Download

Successor Sets and the Axioms of Peano

The pdf document is the full text including the proofs.

Current Version: 1.0.2 from October 2020.