# Unions and Intersections of Sets

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 Unions and Intersections of Sets. 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:

Axioms ZFC-0 to ZFC-4 are explained in the unit Universe. Axioms ZFC-5 to ZFC-7 will be explained in the present unit. 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].

Axioms ZFC-0 to ZFC-4 are as follows:

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

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

Axiom. ZFC-1: Axiom of Extension 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$.

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

Axiom. ZFC-3: Axiom of Specification Let $A$ be a set, and let $\varphi = \varphi(x)$ be a sentence (for the definition of a sentence see Unit Universe) 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) \}.$$

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$. (The intersection $A \cap B$ of two sets $A$ and $B$ will be defined in Definition [#nst-def-intersection].)

The above mentioned axioms and the subsets are explained in detail in the unit Unit Universe. Some elementary properties of subsets are as follows:

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

(a) We have

$$\emptyset \subseteq A \mbox{ and } A \subseteq A \mbox{ for all sets } A.$$

(b) If

$$A \subseteq B \mbox{ and } B \subseteq A \mbox{ for two sets } A \mbox{ and } B,$$

then we have $A = B$.

(c) If

$$A \subseteq B \mbox{ and } B \subseteq C \mbox{ for three sets } A, B \mbox{ and } C,$$

then we have $A \subseteq C$.

In this unit we will explain the following basic methods of constructing new sets from given sets: the pairing of sets, the union of sets, the intersection of sets, the complement of a set and the power set of a set. For some of these constructions we need specific axioms (Axioms ZFC-5, ZFC-6 and ZFC-7) guaranteeing the existence of these sets.

### The Axiom of Pairing

Let ${\cal U} = [A]$ be the universe consisting of one set $A$ such that $A \notin A$. Obviously, the universe ${\cal U}$ fulfills the basic axiom (it consists of sets, namely the set $A$, and we have defined $A \notin A$). Since the universe ${\cal U}$ consists of only one set, it fulfills the axiom of extension. Since the set $A$ does not contain any element, the set $A$ is the empty set, hence the universe ${\cal U}$ fulfills the axiom of existence.

The set $A$ has only one subset, namely the set $A = \emptyset$. Hence, we have

$$\{ x \in A \mid \varphi(x) \} = \emptyset = A$$

for all sentences $\varphi$ implying that the universe ${\cal U}$ fulfills the axiom of specification.

Finally, the axiom of foundation is a requirement about non-empty sets. Since the universe ${\cal U}$ does not contain non-empty sets, the axiom is obviously fulfilled.

In other words the universe ${\cal U} =[A]$ fulfills all axioms we have introduced so far. So it is obvious that we need some more axioms in order to be able to construct more sets than just the empty set. The first important axiom to construct further sets is the axiom of pairing: Given two sets $A$ and $B$ it guarantees the existence of the sets $\{ A \}$ and $\{ A, B \}$.

For $A := \emptyset$ we obtain the new set $B := \{ A \} = \{ \emptyset \}$ and the new set

$$C := \{ A, B \} = \{ \emptyset, \{ \emptyset \} \}.$$

In addition, we will use the axiom of pairing and the axiom of foundation to exclude constellations like

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

### Unions of Sets

Suppose that we have the two sets $A = \{ a, b, c \}$ and $B = \{ b, c, d \}$. We want to be able to construct the set $C$ containing all elements of the set $A$ and the set $B$, in other words, we want to construct the set

$$C := A \cup B = \{ a, b, c, b, c, d \} = \{ a, b, c, d \}.$$

To do so we need a further axiom, namely the axiom of unions. It guarantees the existence of the union of arbitrary many sets and not only the union of two sets. More formally, given a set ${\cal C}$ of sets, there exists a set $U$, denoted by

$$U := \bigcup_{C \in {\cal C}} C$$

with the property that

$$x \in U \mbox{ if and only if } \exists \: C \in {\cal C} : x \in C.$$

Let $A$ and $B$ be two sets. Note that we require the existence of the set $\{A, B\}$ in order to build the union

$$A \cup B = \bigcup_{X \in \{A, B\}} X.$$

The axiom of pairing provides the existence of the set $\{A, B\}$ for arbitrary sets $A$ and $B$. For more details see Definition [#nst-def-union].

Above, we have deduced from the axiom of pairing the existence of the sets

$$0 := \emptyset, 1 := \{ \emptyset \} = \{ 0 \}, \mbox{ and } 2 := \{ \emptyset, \{ \emptyset \} \} = \{0, 1 \}.$$

By the axiom of pairing, the set $\{ 2 \}$ exists. Set

$$3 := 2 \cup \{ 2 \} = \{0, 1, 2 \}.$$

By continuing this process, we will be able to define the natural numbers as specific sets, and we will obtain the recursive formula

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

Hence, the axiom of pairing and the axiom of unions are sufficient to construct all natural numbers. However, for the construction of the set $\mathbb{N}_0$ of all natural numbers we will need the additional axiom of infinity. The whole process is explained in the unit [Natural Numbers – in preparation].

### Intersection of Sets

The union $A \cup B$ of two sets $A$ and $B$ is characterized by the assertions $x \in A$ or $x \in B$. The intersection $A \cap B$ of two sets $A$ and $B$ is characterized by the assertions $x \in A$ and $x \in B$. More generally, given a non-empty set ${\cal C}$ of sets, the intersection

$$D := \bigcap_{C \in {\cal C}} C$$

is defined by the property that

$$x \in D \mbox{ if and only if } x \in C \mbox{ for all } C \in {\cal C}.$$

See Definition [#nst-def-intersection]. The existence of the intersection of sets has not to be postulated by a specific axiom (as the existence of the union of sets), but can be deduced from the axiom of specification (see Proposition [#nst-prop-intersection]).

### The Complement of a Set

The set $S := \{ x \in \mathbb{Z} \mid x \mbox{ is a square} \}$ consists of all integers which are squares. Often, one is interested in the “opposite” set, in our example, the set of all integers which are no squares. In other words, we are interested in the set of the elements of the set $\mathbb{Z}$ which are not contained in the set $S$. The corresponding definition is the complement $C$ of a set $B$ in a set $A$ defined as follows:

$$C := \{ x \in A \mid x \notin B \}.$$

The set $C$ is denoted by $C = A \setminus B$ or by $B^c$ if no confusion about the set $A$ may arise.

A main result about complements is the interplay between complements, intersections and unions of sets expressed by de Morgan’s laws (Theorem [#nst-th-de-morgan]). They state

$$(X \cup Y)^c = X^c \cap Y^c \mbox{ and } (X \cap Y)^c = X^c \cup Y^c$$

for all subsets $X$ and $Y$ of a set $A$ where $X^c$ and $Y^c$ denote the complements of the sets $X$ and $Y$ in the set $A$, respectively.

### The Power Set of a Set

Consider the set $A := \{1, 2\}$. It has the four subsets

$$\emptyset, \{ 1 \}, \{ 2 \} \mbox{ and } A = \{ 1, 2\}.$$

The axiom of powers guarantees the existence of the set $\big\{ \emptyset, \{ 1 \}, \{ 2 \}, \{ 1, 2\} \big\}$ of all subsets of the set $A$. More generally, given a set $A$, the axiom of powers guarantees the existence of the set ${\cal P}(A)$ of all subsets of the set $A$. The set ${\cal P}(A)$ is called the power set of the set $A$.

### Historical Note:

The axioms of Zermelo and Fraenkel have been published by E. Zermelo in the two papers Zermelo-1908b and Zermelo-1930. For more details see Unit Universe.

## The Axiom of Pairing

Axiom. Suppose that our universe contains two sets $A$ and $B$. Then we want to guarantee that the universe also contains the sets $\{ A \}$ and $\{ A, B \}$. This is the content of the axiom of pairing:

Axiom. (ZFC-5: Axiom of Pairing) Let $A$ and $B$ be two sets.

(a) There exists the set ${\cal C} := \{ A \}$.

(b) There exists the set ${\cal D} := \{ A, B \}$.

French / German. Axiom of Pairing = Axiome de la paire = Paarmengenaxiom.

Remark. Of course the question arises what about the existence of the set $\{ A, B, C \}$ for three given sets $A$, $B$ and $C$? More generally, what about the sets

$$\{ A_1, \ldots, A_n \} \mbox{ or } \{A_i \mid i \in I \}$$

for $n$ given sets $A_1, \ldots, A_n$ or for a given family $\big( A_i \big)_{i \in I}$ of sets? In fact, all these sets exist: Given three sets $A$, $B$ and $C$ the axiom of pairing provides the sets $\{ A, B \}$ and $\{ B, C \}$. The axiom of unions provides the set

$$\{ A, B \} \cup \{ B, C \} = \{ A, B, C \}.$$

The existence of the set $\{ A_1, \ldots, A_n \}$ follows by a simple induction argument. Natural numbers and the principle of induction are explained in the unit [Natural Numbers – in preparation]. For the existence of the set $\{ A_i \mid i \in I \}$ we first have to define what a family $\big( A_i \big)_{i \in I}$ of sets is. This is done in the unit Families. Then the existence of the set $\{ A_i \mid i \in I \}$ will follow from the axiom of substitution (ZFC-8) which is also explained in the unit Families.

We can draw the following conclusions from the axiom of foundation and the axiom of pairing:

Theorem. (a) Let $A$ be a set. Then we have $A \notin A$.

(b) Let $A$ and $B$ be two sets. If the set $A$ is an element of the set $B$, then the set $B$ is no element of the set $A$.

(c) Let $A$ and $B$ be two sets. If the set $A$ is a subset of the set $B$, then the set $B$ is no element of the set $A$.

### Historical Note:

The axiom of pairing has been introduced by Zermelo in his first article about the axiomatization of mathematics:

Axiom II. (Axiom der Elementarmengen) […] Ist $a$ irgend ein Ding des Bereichs, so existiert eine Menge $\{ a \}$, welche $a$ und nur $a$ als Element enthält; sind $a$, $b$ zwei Dinge des Bereiches, so existiert immer eine Menge $\{ a, b \}$, welche sowohl $a$ als $b$, aber kein von beiden verschiedenes Ding $x$ als Element enthält.

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

Axiom II. (Axiom of elementary sets) […] If $a$ is any object of the domain, there exists a set $\{ a\}$ containing $a$ and only $a$ as element; if $a$ and $b$ are any two objects of the domain, there alway exists a set $\{ a, b\}$ containing as elements $a$ and $b$ but no object $x$ distinct from both.

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

The word domain stands for set.

Zermelo had introduced the axiom of foundation in his second article about the axiomatization of mathematics based on previous work of Abraham Fraenkel and John von Neumann. For details see Unit Universe. In this article he also mentions the contents of Theorem [#nst-th-x-notin-x]:

Dieses letzte Axiom [Axiom der Fundierung], durch welches alle zirkelhaften namentlich auch alle sich selbst enthaltenden, überhaupt alle wurzellosen Mengen ausgeschlossen werden, war bei allen praktischen Anwendungen der Mengenlehre bisher immer erfüllt, bringt also vorläufig keine wesentliche Einschränkung der Theorie.

See [Zermelo-1930], p. 31.

This last axiom [axiom of foundation], by which all circular sets, in particular all sets containing themselves, and all sets without roots are excluded, has been fulfilled so far in all practical applications of set theory. Thus it does not result in a substantial restriction of the theory for now.

(Translation by the author.)

## Unions of Sets

### The Axiom of Unions:

Axiom. (ZFC-6: Axiom of Unions) Let ${\cal C}$ be a set. Then there exists a set $U$ consisting of the elements $x$ that are contained in at least one element of the set ${\cal C}$, that is,

$$x \in U \mbox{ if and only if there exists an element C of the set {\cal C} such that } x \in C.$$

Axiom of unions = Axiome de la Réunion = Vereinigungsaxiom.

### Definition of the Union:

Definition. (a) Let ${\cal C}$ be a set, and let $U$ be the set consisting of the elements $x$ that are contained in at least one element of the set ${\cal C}$. The set $U$ is called the {\bf union of the set ${\cal C}$}.

The set $U$ is denoted by

$$U := \bigcup_{C \in {\cal C}} C \: \mbox{ or, equivalently, by } U := \bigcup \{ C \mid C \in {\cal C} \}.$$

(b) If the set ${\cal C} = \{A, B\}$ consists of two sets $A$ and $B$, then we write $U := A \cup B$.

French / German. Union = Réunion = Vereinigungsmenge.

Note that it follows from the axiom of unions that the set $U := \bigcup_{C \in {\cal C}} C$ exists for all sets ${\cal C}$.

### Elementary Properties of the Union of Sets:

Theorem. Let $A$ and $B$ be two sets. Then the union $A \cup B$ exists.

Example. Suppose that the sets $A := \{a, b\}$ and $B := \{b, c\}$ exist. Then we have

$$A \cup B = \{a, b, c\}.$$

Proposition. Let ${\cal C} = \emptyset$. Then we have $\bigcup_{C \in {\cal C}} C = \emptyset$.

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

(a) We have $A \subseteq A \cup B$ and $B \subseteq A \cup B$.

(b) We have $A = \{ x \in A \cup B \mid x \in A\}$ and $B = \{ x \in A \cup B \mid x \in B\}$.

(c) We have $A \cup \emptyset = A$ and $A \cup A = A$.

(d) We have $A \cup B = B \cup A$ (commutativity).

(e) We have $(A \cup B) \cup C = A \cup (B \cup C)$ (associativity).

(f) We have $A \subseteq B$ if and only if $A \cup B = B$.

Examples. (a) If $\{a\}$ and $\{b\}$ are two sets, then we have $\{a\} \cup \{b\} = \{a, b\}$.

(b) If $\{a\}$, $\{b\}$ and $\{c\}$ are three sets, then we have $\{a\} \cup \{b\} \cup \{c\} = \{a, b, c\}$.

### Historical Note:

The axiom of unions has been introduced by Zermelo in his first article about the axiomatization of mathematics:

Axiom V. (Axiom der Vereinigung) Jeder Menge $T$ entspricht eine Menge $\mathfrak{S} T$ (die Vereinigungsmenge} von $T$), welche alle Elemente der Elemente von $T$ und nur solche als Elemente enthält.

See [Zermelo-1908b], p. 265.

Axiom V. (Axiom of the union) To every set $T$ there corresponds a set $\mathfrak{S} T$, the union of $T$, that contains as elements precisely all elements of the elements of $T$.

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

The letter $\mathfrak{S}$ stands for {\em Summe} (sum). So we have

$$\mathfrak{S} T = \bigcup_{X \in T} X.$$

As for many other axioms the axiom of unions can already be found in the article about natural numbers by Richard Dedekind:

8. Erklärung. Unter dem aus irgendwelchen Systemen $A, B, C, \ldots$ zusammengesetzten System, welches mit $\mathfrak{M}(A, B, C, …)$ bezeichnet werden soll, wird dasjenige System verstanden, dessen Elemente durch folgende Vorschrift bestimmt werden: ein Ding gilt dann und nur dann als Element von $\mathfrak{M}(A, B, C, …)$, wenn es Element von irgendeinem der Systeme $A, B, C, \ldots$, d.h. Element von $A$ oder $B$ oder $C$ … ist. […]

See [Dedekind-1888] or [Dedekind-CW]. p. 346.

8. Explanation. We understand by a system aggregated by arbitrary systems $A, B, C, \ldots$ and denoted by $\mathfrak{M}(A, B, C, …)$ the system whose elements are defined by the following rule: a thing is considered as an element of $\mathfrak{M}(A, B, C, …)$ if and only if it is an element of one of the systems $A, B, C, \ldots$, that is, if it is an element of $A$ or $B$ or $C$ … . […]

(Translation by the author.)

Dedekind uses the word system for sets. A thing stands for an element of a set. Note that the definitions of a union by Zermelo and by Dedekind differ in an important point: Zermelo requires that the sets $A, B, C, \ldots$ are contained in a common set $T$, whereas Dedekind allows the union

$$A \cup B \cup C \cup \ldots$$

without any restrictions. In fact, Dedekind does not really explain what is meant by “…”. The definition of Zermelo is more precise.

## Intersections of Sets

### Definition of the Intersection:

Proposition. Let $\emptyset \neq {\cal C}$ be a non-empty set. Then there exists a set $D$ consisting of the elements $x$ that are contained in all elements of the set ${\cal C}$, that is,

$$x \in D \mbox{ if and only if } x \in C \mbox{ for all } C \in {\cal C}.$$

Definition. (a) Let $\emptyset \neq {\cal C}$ be a non-empty set. The set $D$ consisting of the elements $x$ that are contained in all elements of the set ${\cal C}$ is called the intersection of the set ${\cal C}$}.

(b) The set $D$ is denoted by

$$D := \bigcap_{C \in {\cal C}} C \: \mbox{ or, equivalently, by } D := \bigcap \{C \mid C \in {\cal C} \}.$$

(c) If the set ${\cal C} = \{A, B\}$ consists of two sets $A$ and $B$, then we write $D := A \cap B$.

French / German. Intersection = Intersection = Durchschnitt.

Remark. In opposite to the union of sets, the empty intersection ($\cap_{C \in {\cal C}} C$ with ${\cal C} = \emptyset$) is not defined. }

Example. Let $A := \{a, b\}$ and $B := \{b, c\}$. If $a \neq c$, we have $A \cap B = \{ b \}$. If $a = c$, we have $A \cap B = \{ a, b \} = \{ b, c \}$. }

### Elementary Properties of the Intersection of Sets:

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

(a) We have $A \cap B \subseteq A$ and $A \cap B \subseteq B$.

(b) We have $A \cap B = \{ x \in A \mid x \in B\} = \{ x \in B \mid x \in A\}$.

(c) We have $A \cap \emptyset = \emptyset$ and $A \cap A = A$.

(d) We have $A \cap B = B \cap A$ (commutativity).

(e) We have $(A \cap B) \cap C = A \cap (B \cap C)$ (associativity).

(f) We have $A \subseteq B$ if and only if $A \cap B = A$.

Proposition. Let $\emptyset \neq {\cal C}$ be a non-empty set, and let $A$ be an element of the set ${\cal C}$.

(a) We have $\bigcap \{ X \mid X \in {\cal C} \} \subseteq A$.

(b) We have $A \subseteq \bigcup \{ X \mid X \in {\cal C} \}$.

The following proposition shows that the union of sets corresponds to the logical or and that the intersection of sets corresponds to the logical and.

Proposition. Let $A$ and $B$ be two sets, and let $\emptyset \neq {\cal C}$ be a non-empty set.

(a) We have $x \in A$ and $x \in B$ if and only if $x \in A \cap B$.

(b) We have $x \in A$ or $x \in B$ if and only if $x \in A \cup B$.

(c) We have $x \in C$ for all elements $C$ of the set ${\cal C}$ if and only if

$$x \in \bigcap \{C \mid C \in {\cal C}\}.$$

(d) There exists an element $C$ of the set ${\cal C}$ containing an element $x$ if and only if

$$x \in \bigcup \{C \mid C \in {\cal C}\}.$$

Proposition. Let $A$, $X$ and $Y$ be three sets, and let $\emptyset \neq {\cal C}$ be a non-empty set.

(a) If $A \subseteq X$ and $A \subseteq Y$, then we have $A \subseteq X \cap Y$.

(b) If $X \subseteq A$ and $Y \subseteq A$, then we have $X \cup Y \subseteq A$.

(c) If $A \subseteq X$ for all elements $X$ of ${\cal C}$, then we have $A \subseteq \bigcap_{C \in {\cal C}} C$.

(d) If $X \subseteq A$ for all elements $X$ of ${\cal C}$, then we have $\bigcup_{C \in {\cal C}} C \subseteq A$.

### Intersections and Unions of Sets:

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

(a) We have

$$(A \cup B) \cap C = (A \cap C) \cup (B \cap C).$$

(b) We have

$$(A \cap B) \cup C = (A \cup C) \cap (B \cup C).$$

### Definition of Disjoint Sets:

Definition. (a) Two sets $A$ and $B$ are called disjoint if their intersection is empty, that is, if we have $A \cap B = \emptyset$.

(b) If $A$ and $B$ are two disjoint sets, then we denote their union $U := A \cup B$ by $U = A \mathbin{\dot{\cup}} B$.

French / German. Disjoint = Disjoint = Disjunkt.

Example. Let $A := \{ a, b, c \}$ be a set such that the elements $a$, $b$ and $c$ are pairwise distinct. Then we have

$$A = A \mathbin{\dot{\cup}}\emptyset = \{a, b\} \mathbin{\dot{\cup}}\{c\} = \{a, c\} \mathbin{\dot{\cup}}\{b\} = \{b, c\} \mathbin{\dot{\cup}}\{a\} = \{a\} \mathbin{\dot{\cup}}\{b\} \mathbin{\dot{\cup}}\{c\}.$$

### Historical Note:

The intersection of sets is – as the union of sets – already defined in the fundamental articles of Zermelo and Dedekind:

8. Sind $M$, $N$ irgend zwei Mengen, so bilden nach III [axiom of extension] diejenigen Elemente von $M$, welche gleichzeitig Elemente von $N$ sind, die Elemente einer Untermenge $D$ von $M$, welche auch Untermenge von $N$ ist und alle $M$ und $N$ gemeinsamen Elemente umfaßt. Diese Menge $D$ wird der gemeinsame Bestandteil oder der Durchschnitt der Mengen $M$ und $N$ genannt und mit $[M, N]$ bezeichnet. […]

9. Ebenso existiert auch für mehrere Mengen $M, N, R, \ldots$ immer ein Durchschnitt $D = [M, N, R, \ldots]$. […]

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

8. If $M$ and $N$ are any two sets, then according to Axiom III [axiom of extension] all those elements of $M$ that are also elements of $N$ are the elements of a subset $D$ of $M$; $D$ is also a subset of $N$ and contains all elements common $M$ and $N$. This set $D$ is called the common component, or intersection, of the sets $M$ and $N$ and is denoted by $[M, N]$. […]

9. Likewise, for several sets $M, N, R, \ldots$ there always exists an intersection $D = [M, N, R, \ldots]$. […]

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

The above propositions are also contained in [Zermelo-1908b], and Zermelo refers to Ernst Schröder’s Vorlesungen über die Algebra der Logik [Schroeder-1890] for a detailed discussion of logical addition and multiplication.

The intersections of sets and their elementary properties are already contained in Dedekind’s introduction of the natural numbers:

17. Erklärung. Ein Ding $g$ heißt gemeinsames Element der Systeme $A, B, C, \ldots$, wenn es in jedem dieser Systeme (also in $A$ und in $B$ und in $C$, …) enthalten ist […], und unter der Gemeinheit der Systeme $A, B, C, \ldots$ verstehen wir das vollständig bestimmte System $\mathfrak{S}(A, B, C, \ldots)$, welches aus allen gemeinsamen Elementen $g$ von $A, B, C, \ldots$ besteht […].

See [Dedekind-1888] or [Dedekind-CW], p.347.

17. Explanation. A thing $g$ is called a common element of the systems $A, B, C, \ldots$ if it is contained in any of these systems (hence in $A$ and in $B$ and in $C$, …) […], and by the intersection of these systems $A, B, C, \ldots$ we understand the completely determined system $\mathfrak{S}(A, B, C, \ldots)$ which consists of all common elements $g$ of $A, B, C, \ldots$ […].

(Translation by the author.)

## The Complement of a Set

### Definition of the Complement:

Definition. (a) Let $A$ and $B$ be two sets, and let $D := \{ x \in A \mid x \notin B \}$ be the set of the elements of the set $A$ which are not contained in the set $B$.

(b) The set $D$ is called the difference between the sets $A$ and $B$} or, equivalently, the complement of the set $B$ in the set $A$.

(c) The set $D$ is denoted by $A \setminus B$.

French / German. Complement = Complément = Komplement.

Example. Let $A := \{a, b\}$ and $B := \{b, c\}$, and suppose that the elements $a$, $b$ and $c$ are pairwise distinct. Then we have $A \setminus B = \{a\}$.

### Elementary Properties of the Complement:

Proposition. Let $A$ and $B$ be two sets. Then we have $A \setminus B = A \setminus (A \cap B)$.

In view of Proposition [#nst-prop-complement-subset] we can alway assume that the set $B$ is a subset of the set $A$ if we consider the difference $A \setminus B$.

Proposition. Let $A$ be a set. For each subset $B$ of the set $A$, let $B^c := A \setminus B$ denote the complement of the set $B$ in the set $A$.

(a) We have $\emptyset^c = A$ and $A^c = \emptyset$.

(b) We have $\left( B^c \right)^c = B$ for all subsets $B$ of the set $A$.

(c) We have $B \cup B^c = A$ and $B \cap B^c = \emptyset$, that is, $A = B \mathbin{\dot{\cup}} B^c$ for all subsets $B$ of the set $A$.

(d) We have

$$X \subseteq Y \mbox{ if and only if } Y^c \subseteq X^c \mbox{ for all } X, Y \subseteq A.$$

### The Complement of Unions and Intersections:

Theorem. De Morgan’s Laws Let $A$ be a set. For each subset $B$ of the set $A$, let $B^c := A \setminus B$ denote the complement of the set $B$ in the set $A$.

(a) We have $(X \cup Y)^c = X^c \cap Y^c$ for all subsets $X$ and $Y$ of the set $A$.

(b) We have $(X \cap Y)^c = X^c \cup Y^c$ for all subsets $X$ and $Y$ of the set $A$.

### Historical Note:

The existence of the complement of a set is considered in the introduction of the axioms by Zermelo:

7. Ist $M_1 \subseteq M$, so besitzt $M$ immer eine Untermenge $M – M_1$, die Komplementärmenge von $M_1$, welche alle diejenigen Elemente von $M$ umfaßt, die nicht Elemente von $M_1$ sind. […]

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

7. If $M_1 \subseteq M$, then $M$ always possesses another subset $M – M_1$, the complement of $M_1$, which contains all those elements of $M$ that are not elements of $M_1$. […]

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

De Morgan’s laws (Theorem [#nst-th-de-morgan]) have been published by de Morgan in [de-Morgan-1864]. They have been published as a result about logic and not about set theory: Union and intersection have to be replaced by OR and AND, and the complement has to be replaced by the negation. Hence, the laws of de Morgan read as follows:

$$\neg (x \lor y) = \neg x \land \neg y \mbox{ and } \neg (x \land y) = \neg x \lor \neg y.$$

The notation of de Morgan is quite different from our current notation. In [de-Morgan-1864], the expression $x \land y$ is called the compound of the expressions $x$ and $y$ and is denoted by $xy$, whereas the expression $x \lor y$ is called the aggregate of the expressions $x$ and $y$ and is denoted by $(x, y)$. Given an expression $x$ the negation $\neg x$ is denoted by the letter $X$, whereas the negation $\neg X$ is denoted by $x$. The laws of de Morgan read as follows:

The contrary of an aggregate is the compound of the contraries of the aggregants: the contrary of a compound is the aggregate of the contraries of the components. Thus $(A, B)$ and $AB$ have $ab$ and $(a, b)$ for contraries.

See [de-Morgan-1864], p. 208.

For more information see for example the article of Michael Schroeder about the history of the notation of Boole’s algebra [Schroeder-1997], in particular p. 50.

The signs $\cup$, $\cap$ and $-$ (for $A \setminus B = A – B$) have been introduced by Giuseppe Peano:

2. Colla scrittura $A \cap B \cap C \ldots$, ovvero $ABC \ldots$, intenderemo la massima classe contenuta nelle classi $A, B, C, \ldots$ ossia la classe formata da tutti gli enti che sono ad un tempo $A$ e $B$ e $C$, ecc. Il segno $\cap$ si leggerà e; […]

3. Colla scrittura $A \cup B \cup C \ldots$, intenderemo la minima classe contiene le classi $A, B, C, \ldots$ ossia la classe formata dagli enti che sono o $A$ o $B$ o $C$, ecc. Il segno $\cup$ si leggerà o; […]

4. Colla scrittura $-A$, ovvero $\bar{A}$, intenderemo la classe formata da tutti gli enti non appartenenti alla classe $A$. Il segno $-$ si leggerà non; […]

See [Peano-1888], pp. 1 – 2.

2. Writing $A \cap B \cap C \ldots$, or $ABC \ldots$, we shall understand the maximal class contained in the classes $A, B, C, \ldots$, that is, the class formed by all the entities that are at the same time $A$ and $B$ and $C$, etc. The sign $\cap$ is read and; […]

3. Writing $A \cup B \cup C \ldots$, we shall understand the minimal class containing the classes $A, B, C, \ldots$, that is, the class formed by the entities which are $A$ or $B$ or $C$, etc. The sign $\cup$ is read or; […]

4. Writing $-A$ or $\bar{A}$ we shall understand the class formed by all the entities which are not contained in the class $A$. The sign $-$ reads non; […]

(Translation by the author.)

## The Power Set of a Set

### The Axiom of Powers:

Axiom. (ZFC-7: The Axiom of Powers) Let $X$ be a set. Then the set of all subsets of the set $X$ exists.

French / German. The Axiom of Powers = Axiome de l’ensemble des parties = Potenzmengenaxiom.

### Definition of the Power Set:

Definition. Let $X$ be a set. Then the set of all subsets of the set $X$ is called the power set of the set $X$. It is denoted by ${\cal P}(X)$.

French / German. Power set = Ensemble des parties d’un ensemble = Potenzmenge.

Examples. (a) Let $X := \emptyset$ be the empty set. Then we have ${\cal P}(X) = \{ \emptyset \}$. Note that the set ${\cal P}(X) = \{ \emptyset \}$ is not the empty set, but a set containing exactly one element, namely the empty set.

(b) Let $X := \{x\}$ be a set containing exactly one element $x$. Then we have ${\cal P}(X) = \big\{ \emptyset, \{x\} \big\}$. Note that the set ${\cal P}(X) = \big\{ \emptyset, \{x\} \big\}$ does not contain the element $x$.

(c) Let $X := \{x, y\}$ be a set containing exactly two elements $x$ and $y$ with $x \neq y$. Then we have ${\cal P}(X) = \big\{ \emptyset, \{x\}, \{y\}, \{x, y\} \big\}$.

### Elementary Properties of the Power Set:

Proposition. Let $X$ be a set, and let $P := {\cal P}(X)$ be the power set of the set $X$. Then the empty set $\emptyset$ and the set $X$ are contained in the set $P$.

Theorem. Let $A$ be a set, and let $\varphi$ be a sentence. Then the following set exists:

$$\{ X \subseteq A \mid \varphi(X) \}.$$

### Historical Note:

The axiom of powers has been introduced by Zermelo:

Axiom IV. (Axiom der Potenzmenge) Jeder Menge $T$ entspricht eine zweite Menge $\mathfrak{U}T$ (die Potenzmenge von $T$), welche alle Untermengen von $T$ und nur solche als Elemente enthält.

See [Zermelo-1908b], p. 265.

Axiom IV. (Axiom of the power set) To every set $T$ there corresponds another set $\mathfrak{U}T$, the power set of $T$, that contains as elements precisely all subsets of $T$.

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

## Notes and References

I found many interesting historical facts in the book Labyrinths of Thought by José Ferreirós [Ferreiros-1999] and in the biography of Ernst Zermelo by Heinz-Dieter Ebbinghaus [Ebbinghaus-2010]. A very good source is also the book Einführung in die Mengenlehre by Oliver Deiser [Deiser-2020] (in German) which contains many historical details.

### Literature

[de-Morgan-1864] De Morgan, Augustus (1864). “On the Syllogism No. III, and on Logic in General”. In: Transactions of the Cambridge Philosophical Society 10, pp. 173–230.

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

[Deiser-2020] Deiser, Oliver (2020). Einführung in die Mengenlehre. Die Mengenlehre Cantors und ihre Axiomatisierung durch Ernst Zermelo. url: www.aleph1.info (visited on 03/14/2020).

Earlier versions of this book have been published at Springer Verlag, Berlin, Heidelberg, New York.

[Ebbinghaus-2010] Ebbinghaus, Heinz-Dieter (2010). Ernst Zermelo. An Approach to His Life and Work. Berlin, Heidelberg, and New York: Springer Verlag.

[Ferreiros-1999] Ferreirós, José (1999). Labyrinths of Thought. A History of Set Theory and its Role in Modern Mathematics. Vol. 23. Historical Studies. Basel: Birkhäuser.

[Peano-1888] Peano, Giuseppe (1888). Calcolo Geometrico secondo l’Ausdehnungslehre di H. Grassmann. Torino: Fratelli Bocca Editori.

[Schroeder-1890] Schröder, Ernst (1890). Vorlesungen über die Algebra der Logik. Vol. 1. Leipzig: Teubner-Verlag.

[Schroeder-1997] Schroeder, Michael (1997). “A Brief History of the Notation of Boole’s Algebra”. In: Nordic Journal of Philosophical Logic 2.1, pp. 41–62.

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

[Zermelo-1930] Zermelo, Ernst (1930). “Über Grenzzahlen und Mengenbereiche”. In: Fundamenta Mathematicae 16, pp. 29– 47.

[Zermelo-1908b-en] Zermelo, Ernst (1967). “Investigations in the Foundations of Set Theory I”. In: From Frege to Gödel. A Source Book in Mathematical Logic, 1879 – 1931. Ed. by van Heijenoort, pp. 199–215.