# The Mathematical Universe

- Introduction
- The Mathematical Universe
- Subsets and the Axiom of Extension
- Sentences
- The Axiom of Specification
- The Axiom of Foundation
- Notes and References
- Download

## Introduction

Please note that the text on this web page gives a summary of the Unit *The Mathematical Universe*. A full text including the proofs is available as a separate pdf document at the end of this page.

The most prominent system of axioms for mathematics is the axiomatics of Zermelo and Fraenkel abbreviated by ZFC where the letter C stands for the axiom of choice. It consists of the following axioms:

ZFC-0: | Basic Axiom |

ZFC-1: | Axiom of Extension |

ZFC-2: | Axiom of Existence |

ZFC-3: | Axiom of Specification |

ZFC-4: | Axiom of Foundation |

ZFC-5: | Axiom of Pairing |

ZFC-6: | Axiom of Unions |

ZFC-7: | Axiom of Powers |

ZFC-8: | Axiom of Substitution |

ZFC-9: | Axiom of Choice |

ZFC-10: | Axiom of Infinity |

The present unit explains the axioms ZFC-0 to ZFC-4. Axioms ZFC-5 to ZFC-7 are explained in the Unit Unions and Intersections of Sets. Axioms ZFC-8 and ZFC-9 are explained in the Unit Families. Finally, Axiom ZFC-10 is explained in the Unit [Successor Sets – in preparation].

### The mathematical universe:

We will call the totality of mathematics a **mathematical universe** or just a **universe**. Note that we speak of *a* mathematical universe and not of *the* mathematical universe. There may and do exist different mathematical universes with similar properties. You may think of the definition of a group. All groups have the same (defining) properties, however there exist different groups. Our mathematical universes will all obey the same axioms, namely the axioms of Zermelo and Fraenkel listed above, but there do exist different universes fulfilling these axioms.

In principle, we should have to start every definition and every theorem by the words “*Let ${\cal U}$ be a mathematical universe (fulfilling the axioms of Zermelo and Fraenkel), and …*“. However, the mathematical tradition is to omit this expression.

The first main idea is to postulate that a mathematical universe consists of a collection of sets. In other words, every mathematical object is a set. This approach sounds contra-intuitive since we are used to distinguish between sets and their elements like the set $\Bbb{N}_0$ of the natural numbers and its elements $0, 1, 2, \ldots$.

Looking at the simple set $A := \big\{ \{x\}, \{y\} \big\}$ it becomes obvious that there is no strict distinction between sets and elements. The sets $\{x\}$ and $\{y\}$ are at the same time elements of the set $A$. So we make one step further and say that every element is also a set. For example, the natural numbers will be defined as specific sets, namely

$$

0 := \emptyset \mbox{ (empty set)}, 1 := \{0\}, \ldots, n+1 := \{0, 1, 2, \ldots, n\}, \ldots

$$

and so on. For more detailed information about natural numbers see the Unit [Natural Numbers – in preparation].

The second main idea is to postulate that the sets of a universe have the property that for each two sets $A$ and $B$ of the universe we either have

$$

A \in B \mbox{ or } A \notin B.

$$

In other words, we assume that for each two sets $A$ and $B$ of a universe ${\cal U}$, exactly one of the two relations $A \in B$ or $A \notin B$ holds. However, it may be difficult to decide which of the two possibilities is correct for two given sets $A$ and $B$.

This is the main content of the basic axiom.

### Subsets and the axiom of extension:

The basic axiom allows us to define a subset of a set in the usual way: A set $A$ is a **subset** of a set $B$ if every element of the set $A$ is also an element of the set $B$. In this case we write $A \subseteq B$.

Our next task is to postulate when two sets $A$ and $B$ are equal: The axiom of extension answers this question as follows:

Two sets $A$ and $B$ are equal if and only if we have

$$

A \subseteq B \mbox{ and } B \subseteq A.

$$

In this case we write $A = B$. Otherwise, we write $A \neq B$.

We want to exclude the case that a mathematical universe does not contain any sets. Therefore, we will require that each universe contains at least one set, namely the empty set. This is the content of the axiom of existence.

### Sentences:

So far we know what a mathematical universe ${\cal U}$ is, namely a collection of sets with the property that for each two sets $A$ and $B$ of the universe ${\cal U}$ we either have

$$

A \in B \mbox{ or } A \notin B.

$$

The next question that we want to answer is: How do we formulate a mathematical sentence? Or, equivalently: What is the mathematical language? Given two sets $A$ and $B$ of a universe ${\cal U}$, we have introduced the following four possible relations between these two sets:

$$

A \in B, \: A \notin B, \: A = B \mbox{ and } A \neq B.

$$

These four expressions are called **elementary sentences**. They form the elementary part of the mathematical language. Mathematical sentences are then recursively defined, for example by $\varphi \land \psi$ ($\varphi$ and $\psi$) or by $\varphi \lor \psi$ ($\varphi$ or $\psi$) if $\varphi$ and $\psi$ are mathematical sentences. A complete definition of sentences will be given later.

The elementary sentences and the sentences already constitute the mathematical language. Every definition and every theorem can be expressed as a sentence. A definition like the definition of a subset introduced above is nothing else than an abbreviation for a specific sentence.

### The axiom of specification:

We are used to define subsets of a given set by specifying some interesting properties. For example, the set $E$ of the even integers is defined as follows:

$$

E := \{ x \in \Bbb{Z} \mid x \mbox{ even} \} = \{ x \in \Bbb{Z} \mid \exists \: z \in \Bbb{Z} : x = 2z \}.

$$

Note that the expression $\exists \: z \in \Bbb{Z} : x = 2z$ is a sentence. The axiom of specification guarantees the existence of sets like the set $E$: Given a set $A$ and a mathematical property (sentence) $\varphi = \varphi(x)$ depending on a variable $x$, the axiom of specification guarantees the existence of the set

$$

\{ x \in A \mid \varphi(x) \}.

$$

In the above example, $\varphi(x)$ is the sentence $\exists \: z \in \Bbb{Z} : x = 2z$.

However, this set may be empty. An important conclusion of the axiom of specification is Theorem [#nst1-th-no-universe] stating that for each set $A$ of a universe ${\cal U}$, there exists a set $B$ of the universe ${\cal U}$ which is no element of the set $A$. In particular, there does not exist a set $A$ containing all sets of the universe.

### The axiom of foundation:

The axiom of foundation excludes some strange constellations like

$$

A \in A \mbox{ or } (A \in B \mbox{ and } B \in A).

$$

## The Mathematical Universe

### The Basic Axiom and the Definition of a Universe:

**Axiom. (ZFC-0: Basic Axiom)** (a) A **mathematical universe** ${\cal U}$ consists of **sets**.

(b) There is the following relation between the sets of the universe ${\cal U}$: For any two sets $A$ and $B$ of the universe ${\cal U}$, either the set $A$ is an **element** of the set $B$ or the set $A$ is **no** **element** of the set $B$.

(c) If the set $A$ is an element of the set $B$, then we also say that **the set $A$ is contained in the set $B$** or, equivalently that **the element $A$ is contained in the set $B$**. (Note that the expression *$A$ is contained in the set $B$* means $A \in B$ and not $A \subseteq B$ ($A$ is a subset of $B$) as defined in the definition of a subset.)

(d) If the set $A$ is an element of the set $B$, then we write $A \in B$. If the the set $A$ is no element of the set $B$, then we write $A \notin B$.

**French / German.** Universe = Univers = Universum. Set = Ensemble = Menge. Element = Élément = Element

**Remarks. ** (a) Note that we did not define what a set is. We just said that our mathematical universe consists of sets. However, the basic axiom states that there exists a relation between any two sets $A$ and $B$, namely either $A \in B$ or $A \notin B$.

In other words, the mathematical objects are exactly the sets of the universe $\: {\cal U}$. Mathematics can be understood as the study of the relation between these sets.

(b) We are used to think of elements and sets as different objects: For example, the number 1 is an *element* of the *set* $\Bbb{N}_0$ of the natural numbers.

In the axiomatic approach of ZFC every element is itself a set. Even the natural numbers will be constructed as specific sets. For example, the number 1 will be defined to be the set $\{ \emptyset \}$ containing the empty set as its only element. The definition of numbers based on set theory is explained in the Unit [Natural Numbers – in preparation].

When we use expressions of the form *Let $x$ be an element of the set $A$* or *The element $x$ of the set $A$ …*, we want to emphasize that $x$ is an element of the set $A$. Nevertheless, we have to keep in mind that the element $x$ is also a set itself.

(c) Note that for any two sets of the universe, we either have $A \in B$ or $A \notin B$, **and** we either have $B \in A$ or $B \notin A$.

(d) Formally, we always would have to say *Let $\: {\cal U}$ be a universe fulfilling the axioms …* For the moment being we only have introduced the basic axiom ZFC-0. Successively, we will introduce further axioms. During this unit every theorem will refer to a mathematical universe fulfilling the axioms introduced so far.

(e) Note that we often speak of *the* universe and that we require that *the* universe fulfills certain axioms, but there may exist and do exist different universes fulfilling the same axioms, but having different properties (see Example [#nst1-ex-two-universes]).

### Examples of Universes:

**Examples. ** Let ${\cal U}$ and ${\cal V}$ be the universes defined as follows:

(i) The universes ${\cal U}$ and ${\cal V}$ both consist of the two sets $A$ and $B$. We write ${\cal U} = [A, B]$ and ${\cal V} = [A, B]$.

(ii) In the universe ${\cal U}$ we define $A \in A$, $A \in B$, $B \notin A$ and $B \in B$.

(iii) In the universe ${\cal V}$ we define $A \notin A$, $A \in B$, $B \notin A$ and $B \notin B$.

In the universe ${\cal U}$ there exists a set containing all sets of the universe, namely the set $B$, and every set has at least one element.

In the universe ${\cal V}$ there is no set containing all sets of the universe, and there is a set containing no elements, namely the set $A$.

Hence, the universes ${\cal U}$ and ${\cal V}$ consist of the same sets, but have different properties.

**Remarks. ** (a) It is a bit difficult to imagine two sets $A$ and $B$ with the property $A \in A$ or the properties $A \in B$ and $B \in A$.

In this context it may be helpful to think of sets as of mathematical textbooks: For two mathematical textbooks $A$ and $B$, we define $A \in B$ if and only if the book $A$ is cited in the book $B$. It may occur that a book $A$ is cited in a book $B$ and, at the same time, the book $B$ is cited in the book $A$ ($A \in B$ and $B \in A$). A book could also cite itself (not very common, but thinkable) which corresponds to the case $A \in A$.

(b) However, we will exclude these strange possibilities in the axiom of foundation.

### Historical Note:

At the end of the 19th century and in the beginning of the 20th century was a growing interest into set theory. This interest had two main sources:

Richard Dedekind (1831 – 1916) investigated systematically the nature of the natural numbers (see [Dedekind-1888]) and of the real numbers (see [Dedekind-1872]). Georg Cantor (1845 – 1918) started a systematic research on sets and the cardinalities of sets. He started this research with the observation that the cardinality of the set of the real numbers is strictly greater than the cardinality of the set of the natural numbers (see [Cantor-1874]).

On the other hand David Hilbert (1862 – 1943) emphasized the importance of the axiomatization of mathematics and published in 1899 his Grundlagen der Geometrie where he provided a modern axiomatics of a 3-dimensional affine space.

In 1908 Ernst Zermelo published a fundamental paper containing an axiomatics of mathematics based on set theory where he refers explicitly to the former work of Cantor and Dedekind. This paper contains already most of the axioms of Zermelo and Fraenkel listed in the introduction.

The full set of axioms as described in the introduction is only contained in the paper [Zermelo-1930] of Zermelo.

The basic axiom reads in [Zermelo-1908b] as follows:

*1. Die Mengenlehre hat zu tun mit einem Bereich ${\cal B}$ von Objekten, die wir einfach als Dinge bezeichnen wollen, unter denen die Mengen einen Teil bilden. … Von einem Dinge $a$ sagen wir, es existiere, wenn es dem Bereich ${\cal B}$ angehört; […]*

*2. Zwischen den Dingen des Bereiches ${\cal B}$ bestehen gewisse Grundbeziehungen der Form $a \: \varepsilon \: b$. Gilt für zwei Dinge $a$, $b$ die Beziehung $a \: \varepsilon \: b$, so sagen wir $a$ sei Element der Menge $b$ oder $b$ enthalte $a$ als Element oder besitze das Element $a$. Ein Ding $b$, welches ein anderes $a$ als Element enthält, kann immer als eine Menge bezeichnet werden, aber auch nur dann – mit einer einzigen Ausnahme (Axiom II).*

(See [Zermelo-1908b], p. 262.)

*Set theory is concerned with a domain ${\cal B}$ of individuals, which we shall call simply objects and among which are the sets. … We say of an object $a$ that it exists if it belongs to the domain ${\cal B}$; […]*

*2. Certain fundamental relations of the form $a \: \varepsilon \: b$ obtain between the objects of the domain ${\cal B}$. If for two objects $a$ and $b$ the relation $a \: \varepsilon \: b$ holds, we say $a$ is an element of the set $b$, $b$ contains $a$ as an element, or $b$ possesses the element $a$. An object $b$ may be called a set if and – with a single exception (Axiom II) – only if it contains another object, $a$, as an element.*

(See [Zermelo-1908b-en], p. 201.)

It is remarkable that Zermelo does not define what a set is, but that he restricts himself to describe the properties of a set. This approach follows the geometric axiomatics of Hilbert in [Hilbert-1899] where points, lines and planes are not defined, but their properties are described in the corresponding axioms.

Note that Zermelo makes a difference between a set and an object insofar as a set has to contain at least one element (with one exception which is of course the empty set). So the objects of Zermelo are the sets of the basic axiom.

An earlier definition of a set is due to Richard Dedekind who gives the following definition:

*Es kommt sehr häufig vor, dass verschiedene Dinge $a, b, c, \ldots$ … im Geiste zusammengestellt werden, und man sagt dann, dass sie ein System $S$ bilden; man nennt die Dinge $a, b, c, \ldots$ die Elemente des Systems $S$ …; umgekehrt besteht $S$ aus diesen Elementen. Ein solches System $S$ … ist als Gegenstand unseres Denkens ebenfalls ein Ding …*

(See [Dedekind-1888] or [Dedekind-CW], vol. 3, p. 344 – 345.)

*It happens quite often that different things $a, b, c \ldots$ … are summarized in one’s mind’s eye; in this case one says that they form a system $S$; the things $a, b, c, \ldots$ are called the elements of the system $S$ …; conversely, the system $S$ consists of these elements. Such a system $S$ … as an object of our thinking is again a thing …*

(Translation by the author.)

Dedekind distinguishes between elements (things) and sets (systems) and points out that every set (system) is also an element (thing). In our terminology, the sets are the things (and of course the systems) of Dedekind.

The symbol $\in$ has been introduced by Giuseppe Peano (1858 – 1932) as the Greek letter $\varepsilon$:

*Signo $K$ significatur classis, sive entium aggregatio. Signum $\varepsilon$ significat est. Ita $a \: \varepsilon \: b$ legitur $a$ est quoddam $b$; $a \: \varepsilon \: K$ significat $a$ est quaedam classis; $a \: \varepsilon \: P$ significat $a$ est quaedam propositio.*

(See [Peano-1899], p. x.)

*The sign $K$ means class, or aggregate of objects. The sign $\varepsilon$ means is. Thus $a \: \varepsilon \: b$ is read $a$ is a $b$; $a \: \varepsilon \: K$ means $a$ is a class; $a \: \varepsilon \: P$ means $a$ is a proposition.*

(See [Peano-1899-en], p. 89.)

## Subsets and the Axiom of Extension

### Definition of a Subset:

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

(a) The set $A$ is called **a subset of the set $B$** if every element of the set $A$ is also an element of the set $B$. If the set $A$ is a subset of the set $B$, we write $A \subseteq B$.

(b) If the set $A$ is a subset of the set $B$ and if the set $B$ contains an element $b$ not contained in the set $A$, then the set $A$ is called a **proper subset** of the set $B$. In this case we write $A \subset B$.

**French / German.** Subset = Sous-ensemble = Teilmenge; Proper subset = Sous-ensemble propre = Echte Teilmenge.

**Example. ** Let $A$ be a set containing exactly the elements $a$ and $b$, and let $B$ be a set containing exactly the elements $a$, $b$ and $c$.

(a) The set $A$ is a subset of the set $B$.

(b) Since the element $c$ is not contained in the set $A$, the set $A$ is even a proper subset of the set $B$.

### The Axiom of Extension:

**Axiom. (ZFC-1: Axiom of Extension)** (a) Two sets $A$ and $B$ are **equal** if and only if the set $A$ is a subset of the set $B$ and if the set $B$ is a subset of the set $A$.

(b) If the sets $A$ and $B$ are equal, then we write $A = B$. If the sets $A$ and $B$ are not equal, then we write $A \neq B$. Hence, we have

$$

A = B \mbox{ if and only if } A \subseteq B \mbox{ and } B \subseteq A.

$$

**French / German.** Axiom of extension = Axiome d’extensionalité = Extensionalitätsaxiom.

**Definition. ** Let $A$, $B$ and $C$ be three sets. If the sets $A$, $B$ and $C$ contain exactly the elements $a$, $a$ and $b$ and $a$, $b$ and $c$, respectively, then we write $A = \{a\}$, $B = \{a, b\}$ and $C = \{a, b, c\}$, and so on.

**Remarks. ** (a) The axiom of extension can also be expressed by saying that two sets $A$ and $B$ are equal if and only if they contain the same elements.

(b) Every element only appears once in a set $A$. As an example consider the set $A = \{a, b, c\}$ consisting of the elements $a$, $b$ and $c$.

(i) If $a \neq b$ and $b \neq c$ (implying $a \neq c$), then the set $A = \{a, b, c\}$ consists of the elements $a$, $b$ and $c$.

(ii) If $a = b$ and $a \neq c$ (implying $b \neq c$), then we have $A = \{a, b, c\} = \{a, c\} = \{b, c\}$, and the set $A$ consists of the elements $a$ and $b$ or, equivalently, of the elements $b$ and $c$.

(iii) If $a = b$ and $a = c$ (implying $b = c$), then we have $A = \{a, b, c\} = \{a\} = \{b\} =\{c\}$, and the set $A$ consists of one element $a = b = c$.

(c) For a set $A$, we only distinguish between the two cases whether an element $a$ is contained in the set $A$ or not. In particular, the order of the elements does not play any role. For example, we have $\{ a, b \} = \{ b, a \}$.

(d) Note the difference between the two notions *is element of*, that is, $\in$ and *is a subset of*, that is, $\subseteq$: Let $A$ and $B$ be two sets. If the set $A$ is a subset of the set $B$, that is, if $A \subseteq B$, then every element of the set $A$ is an element of the set $B$. If the set $A$ is an element of the set $B$, that is, $A \in B$, then the set $A$ is itself an element of the set $B$.

For example, if the sets $A = \{a, b\}$, $B = \{a, b, c\}$, $C =

\{ \{a\}, \{a, b\} \}$ and $D:= \{ a, b, \{a, b\} \}$ exist, then we have

$$

A \subseteq B, \: A \in C, \: A \subseteq D \mbox{ and } A \in D.

$$

The example shows in particular that we can have $A \in D$ and $A \subseteq D$ at the same time.

**Examples. ** (a) Let ${\cal U}$ be the universe consisting of two (different) sets $A$ and $B$ such that

$$

A \notin A, A \in B , B \in A \mbox{ and } B \notin B.

$$

The universe ${\cal U}$ fulfills the axiom of extension.

(b) Let ${\cal V}$ be the universe consisting of two (different) sets $A$ and $B$ such that

$$

A \in A, A \in B, B \in A \mbox{ and } B \in B.

$$

The universe ${\cal V}$ does not fulfill the axiom of extension since the sets $A$ and $B$ have the same elements, but the sets $A$ and $B$ are supposed to be different.

### Elementary Properties of Sets:

**Proposition. ** Let $A$ be a set.

(a) The set $A$ is a subset of itself, that is, we have $A \subseteq A$.

(b) The set $A$ equals itself, that is, we have $A = A$.

**Proposition. ** Let $A$ and $B$ be sets. We have

$$

A = B \mbox{ if and only if } B = A.

$$

**Proposition. ** Let $A$, $B$ and $C$ be sets.

(a) If we have $A \subseteq B$ and $B \subseteq C$, then we have $A \subseteq C$.

(b) If we have $A = B$ and $B \subseteq C$, then we have $A \subseteq C$.

(c) If we have $A \subseteq B$ and $B = C$, then we have $A \subseteq C$.

(d) If we have $A \subset B$ and $B \subset C$, then we have $A \subset C$.

(e) If we have $A \subseteq B$ and $B \subset C$, then we have $A \subset C$.

(f) If we have $A \subset B$ and $B \subseteq C$, then we have $A \subset C$.

(g) If we have $A = B$ and $B \subset C$, then we have $A \subset C$.

(h) If we have $A \subset B$ and $B = C$, then we have $A \subset C$.

(i) If we have $A = B$ and $B = C$, then we have $A = C$.

### When is $A \not\subseteq B$?

**Proposition. ** Let $A$ and $B$ be two sets. Then the following conditions are equivalent:

(i) The set $A$ is no subset of the set $B$.

(ii) There exists an element $a$ of the set $A$ which is not contained in the set $B$.

### The Empty Set and the Axiom of Existence:

**Definition. ** A set which does not contain any element is called **empty**.

**French / German.** Empty set = Ensemble vide = Leere Menge

**Axiom. (ZFC-2: Axiom of Existence)** There exists an empty set.

**French / German.** Axiom of existence = Axiome d’existence = Existenzaxiom.

**Remark. ** The axiom of existence means that each universe ${\cal U}$ fulfilling the axiom of existence contains a set $A$ such that

$$

X \notin A \mbox{ for all sets $X$ of the universe } {\cal U}.

$$

**Proposition. ** (a) The empty set is a subset of every set.

(b) If $A$ and $B$ are empty sets, then we have $A = B$, that is, the empty set is unique.

**Definition. ** The empty set is denoted by $\emptyset$.

**Example. ** The universe ${\cal U}$ of Example [#nst1-ex-two-universes]xx does not fulfill the axiom of existence, whereas the universe ${\cal V}$ of Example [#nst1-ex-two-universes] xx does fulfill the axiom of existence.

### Historical Note

An early definition of subsets is given by Richard Dedekind:

*Ein System $A$ heißt Teil eines Systems $S$, wenn jedes Element von $A$ auch Element von $S$ ist.*

(See [Dedekind-1888] or [Dedekind-CW], p.345.)

*A aystem $A$ is called part of a system $S$ if every element of $A$ is also an element of $S$.*

(Translation by the author.)

Dedekind uses the word system for sets. The symbol $\subset$ has been introduced by Ernst Schröder (1841 – 1902):

*Das andere Zeichen $\subset$ lese man: untergeordnet, auch, wenn man will: subordinirt. … Die Kopula ist wird bald die eine, bald die andere der beiden Beziehungen ausdrücken, die wir mittels der Zeichen $\subset$ und $=$ dargestellt haben. Zu Ihrer Darstellung wird sich darum ein aus den beiden letzten zusammengesetztes Zeichen € … empfehlen. Ausführlichst wird dieses Zeichen als untergeordnet oder gleich zu lesen sein.*

(See [Schroeder-1890], p. 129 and p. 132.)

*The other sign $\subset$ is read inferior, or, if you want subordinate. … The copula is will express the one or the other of the two relations that we represent by the signs $\subset$ and $=$. To its representation the sign € built from these two signs commends itself. … In detail this sign has to be read as subordinate or equal. *

(Translation by the author.)

Schröder introduced these signs in the context of logic.

The sign $\subseteq$ instead of € has been used later on by Felix Hausdorff (1868 – 1942) (see [Hausdorff-1914], p. 3).

The axiom of extension has already been introduced by Dedekind:

*Das System $S$ ist daher dasselbe wie das System $T$, in Zeichen $S = T$, wenn jedes Element von $S$ auch Element von $T$ und jedes Element von $T$ auch Element von $S$ ist.*

Footnote: *Auf welche Weise diese Bestimmtheit zustande kommt, und ob wir einen Weg kennen, um hierüber zu entscheiden, ist für alle Folgende gänzlich gleichgültig;*

(See [Dedekind-1888] or [Dedekind-CW], p. 345.)

*The system $S$ is therefore the same as the system $T$, notation $S = T$, if every element of $S$ is also an element of $T$ and if every element of $T$ is also an element of $S$.*

Footnote: *It is completely indifferent for the following how this relation is achieved or whether we know a way how to decide about this relation.*

(Translation by the author.)

Dedekind wants to express in the footnote that the way how an element is constructed does not matter for the decision whether it is element of a set. For example, we have

$$ \{2\} = \{ \sqrt{4} \} = \{ \lim_{n \rightarrow \infty} 2 + \frac{1}{n} \}.$$

We can also speak of the set

$$

A := \{(a, b, c) \in \mathbb{N} \times \mathbb{N} \times \mathbb{N} \mid a^n + b^n = c^n \mbox{ for some } n \geq 3 \}.

$$

Today, we know that $A = \emptyset$. Before the proof of Andrew Wiles and others we did not *know a way how to decide about the relation* $x \in A$.

This is also the reason why this axiom is called the axiom of *extension* in contrary to an axiom of *intension*.

The first almost complete list of axioms is contained in [Zermelo-1908b]: The axiom of extension is called the **Axiom der Bestimmtheit**:

**Axiom I.** Ist jedes Element einer Menge $M$ gleichzeitig Element von $N$ und umgekehrt, ist also gleichzeitig $M$ € $N$ und $N$ € $M$, so ist immer $M = N$. Oder kürzer: jede Menge ist durch ihre Elemente bestimmt.

(See [Zermelo-1908b], p. 263.)

**Axiom I.** (Axiom of extensionality.) If every element of a set $M$ is also an element of $N$ and vice versa, if, therefore, both $M$ € $N$ and $N$ € $M$, then always $M = N$; Or more briefly: Every set is determined by its elements.

(See [Zermelo-1908b-en], p. 201.)

The axiom of existence is also contained in [Zermelo-1908b]: It is part of the so-called **Axiom der Elementarmengen**:

**Axiom II.** Es gibt eine (uneigentliche) Menge, die Nullmenge $0$, welche gar keine Elemente enthält. …

(See [Zermelo-1908b], p. 263.)

**Axiom II.** (Axiom of elementary sets.) There exists a (fictitious) set, the null set, $0$, that contains no element at all. …

(See [Zermelo-1908b-en], p. 202.)

For a long time the empty set has been abbreviated by the number $0$. This fits very well to the definition of the natural numbers: One defines $0 := \emptyset$. The symbol $\emptyset$ for the empty set has been introduced by Bourbaki. See for example [Bourbaki-2006], page E.II,6.

## Sentences

In order to formulate mathematical definitions and theorems, we need a mathematical language. We will choose a set-theoretical language. Its main building blocks are sentences. We start with the so-called elementary sentences:

### Definition of Elementary Sentences:

**Remark. ** Given a universe ${\cal U}$ and two sets $A$ and $B$ of the universe ${\cal U}$ it follows from the basic axiom and the axiom of extension that we always have

$$

( A \in B \mbox{ or } A \notin B) \mbox{ and } ( A = B \mbox{ or } A \neq B).

$$

This fact motivates the following definition of an elementary sentence:

**Definition. ** (a) There are four **elementary sentences**:

(i) The set $A$ is an element of the set $B$, or, equivalently, $A \in B$.

(ii) The set $A$ is no element of the set $B$, or, equivalently, $A \notin B$.

(iii) The sets $A$ and $B$ are equal, or, equivalently, $A = B$.

(iv) The sets $A$ and $B$ are distinct, or, equivalently, $A \neq B$.

(b) The variables appearing in an elementary sentence $\varphi$ are called the **variables of the elementary sentence $\varphi$**. We also say that a variable $x$ **is contained in the elementary sentence $\varphi$**.

**French / German.** Elementary Sentence = Terme élémentaire = Elementare Aussage.

**Example. ** Let $\varphi$ be the elementary sentence *The sets $A$ and $B$ are equal*, that is, $A = B$.

Then the variables $A$ and $B$ are defined by the (elementary) sentence $\varphi$. Both variables are contained in the sentence $\varphi$.

**Remark. ** An (elementary) sentence may be either true or false. If $A$ and $B$ are two sets such that the set $A$ is an element of the set $B$, then the elementary sentence $A \in B$ is true, and the elementary sentence $A \notin B$ is false. So we have carefully to distinguish whether we just formulate an elementary sentence (which may be true or false) or whether we formulate a theorem which is true and has to be proven. It will be clear from the context whether we speak of the sentence $A \in B$ or of the theorem $A \in B$.

In fact, there is a third case: It may be that there exist two different universes ${\cal U}$ and ${\cal V}$ such that the sentence $\varphi$ is true in the universe ${\cal U}$ and false in the universe ${\cal V}$.

A famous example is the continuum hypothesis of G. Cantor: It states that there does not exist any set $X$ fulfilling the following inequalities

$$

|\Bbb{N}_0| < |X| < |\Bbb{R}|

$$

where $|Z|$ denotes the cardinality of the set $Z$ (see Unit [Cardinal Numbers – in preparation]). Paul Cohen proved in [Cohen-1963] and in [Cohen-1964] that there exist two universes ${\cal U}$ and ${\cal V}$ fulfilling the axioms of Zermelo and Fraenkel such that the continuum hypothesis is fulfilled in the universe ${\cal U}$, but not in the universe ${\cal V}$.

**Definition. ** (a) Let $\varphi$ be an elementary sentence. An elementary sentence $\psi$ is called the **negation of the sentence $\varphi$** if and only if we have

$$

\varphi \mbox{ is true if and only if } \psi \mbox{ is false}.

$$

(b) If the elementary sentence $\psi$ is the negation of the the elementary sentence $\varphi$, then we write $\psi =\neg \varphi$.

**Proposition. ** (a) The negations of the elementary sentences are as follows:

Elementary Sentence | Negation |
---|---|

The set $A$ is an element of the set $B$. Equivalently, $A \in B$. | The set $A$ is no element of the set $B$. Equivalently, $A \notin B$. |

The set $A$ is no element of the set $B$. Equivalently, $A \notin B$. | The set $A$ is an element of the set $B$. Equivalently, $A \in B$. |

The sets $A$ and $B$ are equal. Equivalently, $A = B$. | The sets $A$ and $B$ are distinct. Equivalently, $A \neq B$. |

The sets $A$ and $B$ are distinct. Equivalently, $A \neq B$. | The sets $A$ and $B$ are equal. Equivalently, $A = B$. |

(b) The negation of an elementary sentence is again an elementary sentence. For each elementary sentence $\varphi$, there is exactly one negation $\neg \varphi$.

### Definition of Sentences:

**Definition. ** (a) A **sentence** is defined by the following recursive rules:

(i) Every elementary sentence is a sentence.

(ii) If $\varphi$ is a sentence, then the expression *negation of $\varphi$* is a sentence abbreviated by $\neg \varphi$.

The sentence $\neg \varphi$ is defined to be true if and only if the sentence $\varphi$ is false.

(iii) If $\varphi$ and $\psi$ are two sentences, then the expression *$\varphi$ and $\psi$* is a sentence abbreviated by $\varphi \land \psi$.

The sentence $\varphi \land \psi$ is defined to be true if and only if the sentences $\varphi$ and $\psi$ are true.

(iv) If $\varphi$ and $\psi$ are two sentences, then the expression *$\varphi$ or $\psi$* is a sentence abbreviated by $\varphi \lor \psi$.

The sentence $\varphi \lor \psi$ is defined to be true if and only if at least one of the sentences $\varphi$ and $\psi$ is true.

(v) If $\varphi$ and $\psi$ are two sentences, then the expression *If $\varphi$, then $\psi$* is a sentence abbreviated by $\varphi \rightarrow \psi$.

The sentence $\varphi \rightarrow \psi$ is defined to be true if and only if the sentence $\varphi$ is false or if the sentences $\varphi$ and $\psi$ are both true (see Remark [#nst1-rem-sentence]) xx.

(vi) If $\varphi$ and $\psi$ are two sentences, then the expression *$\varphi$ if and only if $\psi$* is a sentence abbreviated by $\varphi \leftrightarrow \psi$.

The sentence $\varphi \leftrightarrow \psi$ is defined to be true if and only if the the sentences $\varphi$ and $\psi$ are both true or both false.

(vii) If $\varphi$ is a sentence, then the expression *There exists a set $X$ such that $\varphi$* is a sentence abbreviated by $\exists \: X \: \varphi$.

The sentence $\exists \: X \: \varphi$ is defined to be true if the sentence $\varphi$ is true for at least one set $X$.

(viii) If $\varphi$ is a sentence, then the expression *For all sets $X$, (we have) $\varphi$* is a sentence abbreviated by $\forall \: X \: \varphi$.

The sentence $\forall \: X \: \varphi$ is defined to be true if the sentence $\varphi$ is true for all sets $X$.

(ix) Let $\varphi$ be a sentence, and let $x$ be a variable of the sentence $\varphi$. If the variable $x$ appears in an expression of the form *for all $x$* ($\forall \: x$) or of the form *there exists an element $x$* ($\exists \: x$), the variable $x$ is called a **bounded variable** of the sentence $\varphi$.

If $x$ and $y$ are two bounded variables of a sentence $\varphi$, then the variables $x$ and $y$ have to be different. This means that the names $x$ and $y$ of the variables have to be different. However, it is possible that $x = y$, that is, the different variables $x$ and $y$ may represent the same set $A$.

(b) The sentence $\exists \: x \: \big(( x \in X) \land \varphi \big)$ is abbreviated by $\exists \: x \in X \: \varphi$. Analogously, the sentence $\forall \: x \: \big(( x \in X) \land \varphi \big)$ is abbreviated by $\forall \: x \in X \: \varphi$.

(c) The variables appearing in a sentence $\varphi$ are called the **variables of the sentence $\varphi$**. We also say that a variable $x$ **is contained in the sentence $\varphi$**.

(d) Let $\varphi$ be a sentence, and let $x$ be a variable of the sentence $\varphi$. If the variable $x$ is not bounded, then it is called a **free variable** or, equivalently, a **parameter** of the sentence $\varphi$.

(e) Formulas without brackets are executed in the following order: $\neg$, $\land$, $\lor$, $\rightarrow$, $\leftrightarrow$.

**French / German.** Sentence = Terme = Aussage. Bounded variable = Variable liée = Gebundene Variable. Free variable = Variable libre = Freie Variable.

**Examples. ** (a) The sentence $\neg \varphi \land \psi \lor \varphi \leftrightarrow \varphi \rightarrow \psi$ means

$$

\Big( \big( (\neg \varphi) \land \psi \big) \lor \varphi \Big) \leftrightarrow (\varphi \rightarrow \psi).

$$

(b) The sentence $(X \in A) \land (X \in B)$ is true if the set $X$ is an element of the set $A$ and an element of the set $B$. The variables $X$, $A$ and $B$ are free variables of this sentence.

(c) The sentence $(\forall X \in A) \rightarrow (X \in B)$ is true if every element of the set $A$ is also contained in the set $B$. The variable $X$ is a bounded variable of this sentence. The variables $A$ and $B$ are free variables.

(d) The sentence $(\forall \: X \in A) \: (\exists \: Y \in B) \: (X = Y)$ is true if each element $X$ of the set $A$ is is also an element of the set $B$. In other words, it says the same as the sentence in (b). The variables $A$ and $B$ are free variables, and the variables $X$ and $Y$ are bounded variables.

(e) Since the sentences in (b) and (c) express the same fact, the following sentence is true:

$$

(\forall A) (\forall B) \Big( \big( (\forall X \in A) \rightarrow (X \in B) \big) \leftrightarrow \big((\forall \: Z \in A) \: (\exists \: Y \in B) \: (Z = Y) \big) \Big).

$$

All variables are bounded.

**Remarks. ** (a) If the variable $X$ is not contained in the sentence $\varphi$, then the sentence *There exists an element $X$ such that $\varphi$* is a sentence with the same meaning as the sentence $\varphi$.

For example, the sentence $\exists \: X \: (A = B)$ has the same meaning as the sentence $A = B$.

(b) If the variable $X$ is not contained in the sentence $\varphi$, then the sentence *For all elements $X$, (we have) $\varphi$* is a sentence with the same meaning as the sentence $\varphi$.

For example, the sentence $\forall \: X (A = B)$ has the same meaning as the sentence $A = B$.

(c) By definition of a sentence, the sentence $\varphi \rightarrow \psi$ is defined to be true if and only if one of the following three cases occurs: 1. $\varphi$ is true and $\psi$ is true. 2. $\varphi$ is false and $\psi$ is true. 3. $\varphi$ is false and $\psi$ is false.

This definition is due to the fact that we want to express that the sentence $\psi$ follows from the sentence $\varphi$, in other words, that the sentence $\psi$ is true if the sentence $\varphi$ is true. If the sentence $\varphi$ is false, the sentence $\psi$ may be true or false.

(d) The condition, that two bounded variables of a sentence $\varphi$ have to be different variables, shall avoid sentences of the form $\forall \: X \: \exists \ X \: \varphi$ instead of $\forall \: X \: \exists \ Y \: \varphi$. However, the sets $X$ and $Y$ may be identical. For example, the sentence

$$

\forall \: X \in A \: \exists \: Y \in B \: (X = Y)

$$

enforces that $X = Y$.

### Negations of Sentences:

**Proposition. ** (a) We have $\neg ( \neg \varphi) \leftrightarrow \varphi$ for all sentences $\varphi$.

(b) We have $(\varphi \land \neg \varphi) \leftrightarrow$ *FALSE* and $(\varphi \lor \neg \varphi) \leftrightarrow$ *TRUE* for all sentences $\varphi$.

(c) The negations of sentences are as follows.

Sentence | Negation |
---|---|

$\varphi \land \psi$. | $\neg \varphi \lor \neg \psi$. |

$\varphi \lor \psi$. | $\neg \varphi \land \neg \psi$. |

$\varphi \rightarrow \psi$. | $\varphi \land (\neg \psi)$. |

$\varphi \leftrightarrow \psi$. | $\varphi \leftrightarrow \neg \psi$. |

$\exists \: X \: \varphi$. | $\forall \: X \: \neg \varphi$. |

$\forall \: X \: \varphi$. | $\exists \: X \: \neg \varphi$. |

**Proposition. ** (a) Let $\alpha$, $\beta$ and $\gamma$ be three sentences. Then we have $(\alpha \land \beta) \land \gamma = \alpha \land (\beta \land \gamma)$ (associativity). We shall simply write $\alpha \land \beta \land \gamma$.

(b) Let $\alpha$, $\beta$ and $\gamma$ be three sentences. Then we have $(\alpha \lor \beta) \lor \gamma = \alpha \lor (\beta \lor \gamma)$ (associativity). We shall simply write $\alpha \lor \beta \lor \gamma$.

(c) Let $\varphi$ and $\psi$ be two sentences. Then we have $\varphi \land \psi = \psi \land \varphi$ (commutativity).

(d) Let $\varphi$ and $\psi$ be two sentences. Then we have $\varphi \lor \psi = \psi \lor \varphi$ (commutativity).

(e) Let $\alpha$, $\beta$ and $\gamma$ be three sentences. Then we have $\alpha \land (\beta \lor \gamma) = (\alpha \land \beta) \lor (\alpha \land \gamma)$ and

$(\alpha \lor \beta) \land \gamma = (\alpha \land \gamma) \lor (\beta \land \gamma)$ (distributive laws).

(f) Let $\alpha$, $\beta$ and $\gamma$ be three sentences. Then we have $\alpha \lor (\beta \land \gamma) = (\alpha \lor \beta) \land (\alpha \lor \gamma)$ and

$(\alpha \land \beta) \lor \gamma = (\alpha \lor \gamma) \land (\beta \lor \gamma)$ (distributive laws).

**Proposition. ** (a) Let $\alpha$, $\beta$ and $\gamma$ be three sentences. Then we have

$$

\big( (\alpha \rightarrow \beta) \land (\beta \rightarrow \gamma)\big) \rightarrow (\alpha \rightarrow \gamma) \mbox{ (implication is transitive)}.

$$

(b) Let $\varphi$ and $\psi$ be two sentences. Then we have $\big((\varphi \rightarrow \psi) \land (\psi \rightarrow \varphi)\big) \leftrightarrow (\varphi \leftrightarrow \psi)$.

(c) The relation $\leftrightarrow$ is an equivalence relation, that is:

(i) We have $\varphi \leftrightarrow \varphi$ for all sentences $\varphi$ (reflexivity).

(ii) Let $\varphi$ and $\psi$ be two sentences. Then we have $(\varphi \leftrightarrow \psi) \leftrightarrow ( \psi \leftrightarrow \varphi)$ (symmetry).

(iii) Let $\alpha$, $\beta$ and $\gamma$ be three sentences. Then we have $\big((\alpha \leftrightarrow \beta) \land (\beta \leftrightarrow \gamma)\big) \rightarrow (\alpha \leftrightarrow \gamma)$ (transitivity).

### Historical Note

Zermelo noticed in [Zermelo-1908b] that a mathematical expression needs to fulfill some formal requirements. He introduced for that purpose the notion *definite*:

*4. Eine Frage oder Aussage ${\cal F}$, über deren Gültigkeit oder Ungültigkeit die Grundbeziehungen des Bereiches vermöge der Axiome und der allgemeingültigen logischen Gesetze ohne Willkür entscheiden, heißt definit.*

(See [Zermelo-1908b], p. 263.)

*4. A question or assertion ${\cal F}$ is said to be definite if the fundamental relations of the domain, by means of the axioms and the universally valid laws of logic, determine without arbitrariness whether it holds or not.*

(See [Zermelo-1908b-en], p. 201.)

The current definition of sentences stems from Thoralf Skolem (1887 – 1963):

.*.. – erwähne ich hier die 5 Grundoperationen der mathematischen Logik. wobei ich die Bezeichnungen E. Schröders [Schroeder-1890] benutze:*

*(1x) Die Konjunktion, … (1+) Die Disjunktion, … (2) Die Negation, … (3x) In jedem Falle Gültigkeit, …(3+) In mindestens einem Falle Gültigkeit, …*

*[…]*

*Unter einer definiten Aussage kann man jetzt einen endlichen Ausdruck verstehen, der von Elementaraussagen der Form $a \in b$ oder $a = b$ mit Hilfe der 5 genannten Operationen aufgebaut ist.*

(See [Skolem-1923].)

*I mention the five basic operations of mathematical logic here, using Schröder’s notation [Schroeder-1890]:*

*(1x) Conjunction, … (1+) Disjunction, … (2) Negation, … (3x) Universal quantification, …(3+) Existential quantification, …*

*[…]*

*By a definite proposition we now mean a finite expression constructed from elementary propositions of the form $a \in b$ or $a = b$ by means of the five operations mentioned.*

(See [Skolem-1923-en], p. 292 – 293.)

## The Axiom of Specification

### The Axiom of Specification:

**Remark. ** So far we have introduced the axiom of extension which defines when two sets are equal and the axiom of existence which guarantees the existence of the empty set. Most of the remaining axioms of Zermelo and Fraenkel will ensure the existence of further sets.

As a next step we would like to construct sets with a certain property, for example, the set of all even natural numbers. A first approach is to guarantee the existence of a set of the form

$$

\{x \mid x \mbox{ is an even natural number} \} = \{ x \mid \exists \: z \in \Bbb{N} : x = 2z \}

$$

or, more generally, to guarantee the existence of a set of the form

$$

\{ x \mid \varphi(x) \}

$$

where $\varphi$ is a sentence containing the variable $x$.

Unfortunately, this approach yields a contradiction: For, consider the set

$$

A := \{ x \mid x \notin x \}.

$$

If the set $A$ itself is an element of the set $A$, that is, if $A \in A$, then it follows that $A \notin A$. If the set $A$ is no element of the set $A$, that is, if $A \notin A$, then it follows that $A \in A$.

It follows that

$$

(A \in A) \rightarrow (A \notin A) \mbox{ and } (A \notin A) \rightarrow (A \in A).

$$

By Proposition [#nst1-prop-implication-transitive], we get

$$

(A \in A) \leftrightarrow (A \notin A),

$$

a contradiction.

Hence, one has to be more careful. The solution is to require the existence of sets of the form

$$

\{ x \in A \mid \varphi(x) \}

$$

for an already existing set $A$ instead of requiring the existence of sets of the form

$$

\{ x \mid \varphi(x) \}.

$$

The resulting axiom of specification still provides a powerful tool to construct subsets of a given set.

**Axiom. (ZFC-3: Axiom of Specification)** Let $A$ be a set, and let $\varphi = \varphi(x)$ be a sentence containing the free variable $x$ (and possibly more variables).

Then there exists a subset $B$ of the set $A$ consisting of all elements $x$ of the set $A$ such that the sentence $\varphi = \varphi(x)$ is true. The set $B$ is denoted by

$$

B := \{ x \in A \mid \varphi(x) \}.

$$

**French / German.** Axiom of specification = Axiome de compréhension or Axiome de séparation = Aussonderungsaxiom.

### Elementary Applications of the Axiom of Specification:

**Examples. ** Let $A$ and $B$ be two sets.

(a) Let $X := \{ x \in A \mid x \neq x \}$. Then the set $X$ is the empty set.

(b) Let $X := \{ x \in A \mid x = a \}$. If the element $a$ is contained in the set $A$, then we have $X = \{a\}$. If the element $a$ is not contained in the set $A$, then the set $X$ is the empty set.

(c) Let $A$ be a set containing the two elements $a$ and $b$. Then we have

$$

\{a, b\} = \{ x \in A \mid x =a \mbox{ or } x = b \}.

$$

(d) Let $a$ be an element of the set $A$, and let $X := \{ x \in A \mid x \neq a \}$. Then the set $X$ consists of all elements of the set $A$ different from the element $a$. The set $X$ is denoted by $A \setminus \{a\}$. For more details see Unit Unions and Intersecions of Sets.

(e) Let $X := \{ x \in A \mid x \in B \}$. The set $X$ consists of all elements contained in the sets $A$ and $B$. The set $X$ is denoted by $X = A \cap B$. Note that $X = \{ x \in B \mid x \in A \}$. For more details see Unit Unions and Intersecions of Sets.

**Remarks. ** (a) Note that it is possible that the set $B := \{ x \in A \mid \varphi(x) \}$ is the empty set. An example is the set $B := \{ x \in A \mid x \neq x \}$ (see Example [#nst1-ex-specification]).

(b) It is important to note that the axiom of specification provides a subset of a *given set* $A$. The axiom of specification provides the existence of the set $\{ x \in A \mid \varphi(x) \}$ and not of a set $\{ x \mid \varphi(x) \}$.

**Definition. ** Let $A$ be a set, let $\varphi$ be a sentence, and let $x$ be a free variable of the sentence $\varphi$.

We say that **an element $a$ of the set $A$ fulfills the condition $\varphi = \varphi(x)$** if the sentence $\varphi(a)$ is true or, equivalently, if the element $a$ is contained in the set $\{ x \in A \mid \varphi(x) \}$.

**Remark. ** One has to be careful with sentences of the form

*Let $x$ be an element fulfilling a condition $\varphi(x)$*.

By the above definition, such a sentence means

*Let $x$ be an element of the set *$\{ x \in A \mid \varphi(x) \}$.

Firstly, one has to specify the set $A$. Secondly, it may be that the set $\{ x \in A \mid \varphi(x) \}$ is empty implying that no such element exists.

### The Non-existence of the Set of all Sets:

**Theorem. ** (a) Let $A$ be an arbitrary set. Then there exists a set $B$ which is no element of the set $A$, that is, $B \notin A$.

(b) There is no set of all sets, that is, there is no set $A$ such that we have $X \in A$ for all sets $X$.

**Remark. ** It follows from Theorem [#nst1-th-no-universe] that the sets of a universe ${\cal U}$ fulfilling axioms ZFC-0 to ZFC-3 cannot be gathered into a set of this universe. Since the mathematical objects of the axiomatics of Zermelo and Fraenkel are only sets, we do not have a notion for the collection of the sets of a universe.

The axiomatic approach of NBG (von Neumann, Bernays and Gödel) extends the mathematical objects from sets to sets and classes. In this axiomatic approach, the collection of the sets of a universe ${\cal U}$ has its place: It is a class. For more details see Unit [The Axiomatics of von Neumann, Bernays and Gödel – in preparation].

### Historical Note:

Georg Cantor defined a set as follows:

*Unter einer Menge verstehen wir jede Zusammenfassung $M$ von bestimmten wohlunterschiedenen mathematischen Objekten $m$ unserer Anschauung oder unseres Denkens (welche die Elemente von $M$ genannt werden) zu einem Ganzen. In Zeichen drücken wir dies so aus:*

$$ M = \{ m \}. $$

(See [Cantor-1895], p. 481.)

*By a set we understand any collection $M$, gathered into a whole, of certain well-distinguished objects $m$ of our perception or our thought (which are called the elements of $M$). We express this by the following notation:*

$$ M = \{ m \}. $$

(Translation by the author based on [Zermelo-1908b-en].)

Comparing this definition with Remark [#nst1-rem-comprehension-no-set] we can say that Cantor’s\ definition of a set is very close to the definition of a set $A$ as

$$

A := \{ x \mid \varphi(x) \}.

$$

It turned out that this definition of sets results in some contradictions which have also been called paradoxes or antimonies. One of the most famous antimonies is the paradox of Bertrand Russell (1872 – 1970) published in the Principles of Mathematics:

*Thus we must conclude again that the classes which as ones are not members of themselves as many do not form a class.*

(See [Russell-1903], No. 102, p. 152.)

A class is a set in our terminology. This paradox is the antimony that we explained in Remark [#nst1-rem-comprehension-no-set].

By the way, in a footnote Zermelo states that he has found this antimony independently from B. Russell before 1903 and that he had communicated it to David Hilbert:

*Indessen hatte ich selbst diese Antinomie unabhängig von Russell gefunden und sie schon vor 1903 u.a. Herrn Prof. Hilbert mitgeteilt.*

(See [Zermelo-1908a], p. 118 – 119.)

*I had , however, discovered this antinomy myself, independently of Russell, and had communicated it prior to 1903 to Professor Hilbert among others.*

(See [Zermelo-1908a-en], p. 191.)

The axiom of specification has been introduced by Zermelo as the *Axiom der Aussonderung*:

**Axiom III.** Ist die Klassenaussage ${\cal F}(x)$ definit für alle Elemente einer Menge $M$, so besitzt $M$ immer eine Untermenge $M_{{\cal F}}$, welche alle diejenigen Elemente $x$ von $M$, für welche ${\cal F}(x)$ wahr ist, und nur solche als Elemente enthält.

(See [Zermelo-1908b], p. 263.)

**Axiom III.** (Axiom of separation.) Whenever the propositional function ${\cal F}(x)$ is definite for all elements of a set $M$, $M$ possesses a subset $M_{{\cal F}}$ containing as elements precisely those elements $x$ of $M$ for which ${\cal F}(x)$ is true.

(See [Zermelo-1908b-en], p. 202.)

The condition that the propositional function ${\cal F}(x)$ is definite means that ${\cal F}(x)$ is a sentence.

The antinomy of Remark [#nst1-rem-comprehension-no-set] becomes the positive existence theorem (Theorem [#nst1-th-no-universe]) stating that for each set $A$ there exists an element (set) $b$ such that $b \notin A$. This conclusion is also already contained in the foundation paper of Zermelo:

*10. Theorem. Jede Menge $M$ besitzt mindestens eine Untermenge $M_0$, welche nicht Element von $M$ ist.*

(See [Zermelo-1908b], p. 264.)

*10. Theorem. Every set $M$ possesses at least one subset $M_0$ that is not an element of $M$.*

(See [Zermelo-1908b-en], p. 203.)

## The Axiom of Foundation

**Remark. ** So far, we have seen some constellations which do not fit very well to our intuitive understanding of sets and elements. Examples of such constellations are

(i) a set $A$ with $A \in A$ (a set which is an element of itself),

(ii) two sets $A$ and $B$ such that $A \in B$ and $B \in A$ at the same time.

The axiom of foundation averts these contra-intuitive constellations.

**Definition. ** Let $A$ and $B$ be two sets. The set

$$

\{ x \in A \mid x \in B \} = \{x \in B \mid x \in A \}

$$

consisting of all elements $x$ contained in both sets $A$ and $B$ is called the intersection of the sets $A$ and $B$ and is denoted by $A \cap B$.

See also Example [#nst1-ex-specification]. Intersections of sets are discussed in more detail in Unit Unions and Intersecions of Sets.

**Definition. ** Let $A$ be a set. An element $a$ of the set $A$ is called **element minimal with respect to the set** $A$ or, equivalently, $\in$-**minimal with respect to the set **$A$ if we have $a \cap A = \emptyset$.

**French / German.** Element minimal = Élément minimal pour l’appartenance = Element-minimal

Condition (ii) of the following proposition explains why these elements are called element minimal:

**Proposition. ** Let $A$ be a set, and let $a$ be an element of the set $A$. Then the following conditions are equivalent:

(i) The element $a$ is element minimal with respect to the set $A$.

(ii) There is no element $x$ of the set $A$ such that $x \in a$.

(iii) We have $x \notin a$ for all elements $x$ of the set $A$.

(iv) We have $a \cap A = \emptyset$.

**Axiom. (ZFC-4: Axiom of Foundation)** Every non-empty set $A$ contains an element $a$ which is element minimal with respect to the set $A$, that is, an element $a$ such that $a \cap A = \emptyset$.

**French / German.** Axiom of Foundation = Axiome de fondation = Fundierungaxiom.

The for us most interesting conclusions of the axiom of foundation can be found in Unit Unions and Intersecions of Sets after the introduction of the axiom of pairing.

### Historical Note:

Ernst Zermelo has updated his list of axioms of 1908 ([Zermelo-1908b-en]) in 1930 and has included the axiom of foundation:

*F) Axiom der Fundierung: Jede (rückschreitende) Kette von Elementen, in welcher jedes Glied Element des vorangehenden ist, bricht mit endlichem Index ab bei einem Urelement. Oder, was gleichbedeutend ist: Jeder Teilbereich $T$ enthält wenigstens ein Element $t_0$, das kein Element $t$ in $T$ hat.*

(See [Zermelo-1930], p. 31.)

*F) Axiom of Foundation: Each (regressive) chain of elements, in which every link is an element of the previous element, terminates with finite index at an ur-element. Or, equivalently: Each set $T$ contains at least one element $t_0$ that has no element $t$ in $T$.*

(Translation by the author.)

Zermelo points out that his axiom of foundation relies on earlier work of Abraham Fraenkel and John von Neumann (1903 – 1957):

**Axiom der Beschränktheit.** Außer den durch die Axiome II bis VII (bzw. VIII) geforderten Mengen existieren keine weiteren Mengen.

(See [Fraenkel-1928], p. 355.)

**Axiom of boundedness.** There do not exist any sets except the sets required by Axioms II to VII (resp. VIII).

(Translation by the author.)

There are the following correspondences: Axiom II – ZFC-5 (axiom of pairing); Axiom III – ZFC-6 (axiom of unions); Axiom IV – ZFC-7 (axiom of powers); Axiom V – ZFC-3 (axiom of specification); Axiom VI – ZFC-9 (axiom of choice); Axiom VII – ZFC-10 (axiom of infinity).

The axiom of boundedness is already mentioned in [Fraenkel-1922], p. 234, but it is not really explained there.

*Es gibt kein II. Ding $a$ mit der folgenden Eigenschaft: Es ist für jede endliche Ordnungszahl (d.h. ganze Zahl) $n$: $[a, n+1] \in [a, n]$.*

(See [von-Neumann-1925], p. 239.)

*There is no II. thing $a$ with the following property: For each finite ordinal number (that is, natural number) $n$: $[a, n+1] \in [a, n]$.*

(Translation by the author.)

A *II. thing* $a$ stands for a function $a$. $[a, n]$ stands for the expression $a(n)$.

## Notes and References

The first book I read about set theory was *Naive Set Theory* by Paul R. Halmos (1916 – 2006) [Halmos-1960}. I still find that it is one of the best introductions into set theory. The units of the mathematical garden about set theory are very much in its spirit.

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

### References:

[Bourbaki-2006] Bourbaki, Nicolas: Théorie des ensembles.

Springer Verlag Berlin, Heidelberg, New York (2006).

This book is a reprint of the edition of 1970. The four chapters of [Bourbaki 2006] have been first published separately in the years 1954 (Description de la mathématique formelle) 1939 and 1954 (Théorie des ensembles), 1956 (Ensembles ordonnés, cardinaux, nombres entiers) and 1956 (Structures).

[Bourbaki-2004] Bourbaki, Nicolas: Theory of Sets.

Springer Verlag Berlin, Heidelberg, New York (2004).

Translation of [Bourbaki 2006] into English.

[Cantor-1874] Cantor, Georg: Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen.

Journal für die reine und angewandte Mathematik **77**, 258 – 262 (1874).

[Cantor-1895] Cantor, Georg: Beiträge zur Begründung der transfiniten Mengenlehre. Mathematische Annalen **46**, 481 – 512 (1895).

[Cohen-1963] Cohen, Paul Joseph: The Independence of the Continuum Hypothesis.

Proceedings of the National Academy of Sciences of the United States of America **50 (6)**, 1143–1148 (1963).

[Cohen-1964] Cohen, Paul Joseph: The Independence of the Continuum Hypothesis II.

Proceedings of the National Academy of Sciences of the United States of America **51 (1)**, 105–110 (1964).

[Dedekind-1872] Dedekind, Richard: Stetigkeit und irrationale Zahlen.

Vieweg, Braunschweig (1872).

[Dedekind-1888] Dedekind, Richard: Was sind und was sollen die Zahlen?

Vieweg, Braunschweig (1888).

[Dedekind-CW] Dedekind, Richard: Gesammelte mathematische Werke.

Eds.: Robert Fricke, Emmy Noether, Öystein Ore.

Vieweg, Braunschweig, Volume 1 (1930), Volume 2 (1931), Volume 3 (1932).

[Fraenkel-1922] Fraenkel, Adolf: Zu den Grundlagen der Cantor-Zermeloschen Mengenlehre.

Mathematische Annalen **86**, 230 – 237 (1922).

[Fraenkel-1928] Fraenkel, Adolf: Einleitung in die Mengenlehre.

3rd edition, Springer Verlag, Berlin (1928).

The first edition appeared in 1919.

[Halmos-1960] Halmos, Paul Richard: Naive Set Theory.

The University Series in Undergraduate Mathematics, D. van Nostrand Company Inc., Princeton, New Jersey (1960).

[Hausdorff-1914] Hausdorff, Felix: Grundzüge der Mengenlehre.

Veit and Comp., Leipzig (1914).

[Hilbert-1899] Hilbert, David: Grundlagen der Geometrie.

Teubner-Verlag, Leipzig (1899).

[Peano-1899] Peano, Ioseph (or Giuseppe): Arithmetices Prinicipia – Nova Methodo Exposita.

Augustae Taurinorum, Romae, Florentiae (1899).

[Peano-1899-en] Peano, Giuseppe: The Principles of Arithmetics – Presented by a new method.

in: [van-Heijenooort-1976], 83 – 97.

This article is a translation of [Peano-1899] into English.

[Russell-1903] Russell, Bertrand: The Principles of Mathematics.

Vol. 1, The University Press, Cambridge (1903).

[Schroeder-1890] Schröder, Ernst: Vorlesungen über die Algebra der Logik.

Vol. 1, Teubner, Leipzig (1890).

[Skolem-1923] Skolem, Thoralf: Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre.

Matematikerkongressen i Helsingfors den 4 – 7 Juli 1922, Den femte skandinaviska matematikerkongressen, Redogörelse.

Akademiska Bokhandeln, Helsinki (1923).

Note that this article is often cited as [Skolem 1922].

[Skolem-1923-en] Skolem, Thoralf: Some remarks on axiomatized set theory.

in: [van-Heijenooort-1976], 290 – 301.

[van-Heijenooort-1976] van Heijenooort, Jean (ed.): From Frege to Gödel. A Source Book in Mathematical Logic, 1879 – 1931.

3rd edition, Harvard University Press, Cambridge Massachusetts (1976).

The first edition appeared in 1967.

[von-Neumann-1925] von Neumann, John: Eine Axiomatisierung der Mengenlehre.

Journal für die reine und angewandte Mathematik **154**, 219 – 240 (1925).

[Zermelo-1908a] Zermelo, Ernst: Neuer Beweis für die Möglichkeit einer Wohlordnung. Mathematische Annalen **65**, 107 – 128 (1908).

[Zermelo-1908a-en] Zermelo, Ernst: A new proof of the possibility of a well ordering.

in: [van-Heijenooort-1976], 183 – 198.

This article is a translation of [Zermelo-1908a] into English.

[Zermelo-1908b] Zermelo, Ernst: Untersuchungen über die Grundlagen der Mengenlehre I. Mathematische Annalen **65**, 261 – 281 (1908).

[Zermelo-1908b-en] Zermelo, Ernst: Investigations in the Foundations of Set Theory I.

in: [van-Heijenooort-1976], 199 – 2015.

This article is a translation of [Zermelo-1908b] into English.

[Zermelo-1930] Zermelo, Ernst: Über Grenzzahlen und Mengenbereiche.

Fundamenta Mathematicae **16**, 29 – 47 (1930).

## Download

The pdf document is the full text including the proofs.

### Change History

Version | Date | Changes |

1.0.0 | March 2020 | Creation |

1.0.1 | April 2020 | New Layout + Minor Corrections |

1.0.2 | April 2020 | Minor Corrections |