Families and the Axiom of Choice

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 Families and the Axiom of Choice. A full text including the proofs is available as a separate pdf-document at the end of this page.

Families and the Axiom of Substitution:

We often use expressions of the form Let $\big( A_i \big)_{i \in I}$ be a family of sets … Intuitively, it is clear what the expression $\big( A_i \big)_{i \in I}$ means.

However, an axiomatic construction of mathematics brings the need to deduce each mathematical expression from the founding axioms. Since we use the axiomatic of Zermelo and Fraenkel (see Unit Universe), we have to define the expression $\big( A_i \big)_{i \in I}$ as a set:

In the unit Functions we have introduced the functions $f : A \rightarrow B$ from a set $A$ into a set $B$ as a specific set. Hence, we can define a family $\big( A_i \big)_{i \in I}$ as a function:

More precisely, an index set $I$ is a non-empty set. If ${\cal A}$ is a set (of sets), then a family is a function

$$
f : I \rightarrow {\cal A}
$$

from an index set $I$ into the set ${\cal A}$. We set $A_i := f(i)$. The function $f : I \rightarrow {\cal A}$ is denoted by $\big( A_i \big)_{i \in I}$.

The advantage of this definition is that we have a formally correct definition of a family within the axiomatic of Zermelo and Fraenkel. In addition, this definition fits very well to our intuitive understanding of a family: For two families $\big( A_i \big)_{i \in I}$ and $\big( B_i \big)_{i \in I}$ we have

$$
\big( A_i \big)_{i \in I} = \big( B_i \big)_{i \in I} \mbox{ if and only if } A_i = B_i \mbox{ for all } i \in I.
$$

See Theorem [#nst-th-family-identical].

Unfortunately, this definition of a family has also a big disadvantage: The family $\big( A_i \big)_{i \in I}$ can only be defined when we have a set ${\cal A}$ such that

$$
A_i \in {\cal A} \mbox{ for all } i \in I.
$$

This is a strong restriction: Let us consider the following example: Let $\big( A_i \big)_{i \in I}$ be a family of sets, and let $C$ be a further set. Suppose that we want to construct the family $\big( B_i \big)_{i \in I}$ by

$$
B_i := A_i \cup C \mbox{ for all } i \in I.
$$

The expression $B_i := A_i \cup C$ looks very innocent, but a family $\big( B_i \big)_{i \in I}$ is a function $g : I \rightarrow {\cal B}$ into a set ${\cal B}$ such that

$$
B_i = g(i) \mbox{ for all } i \in I.
$$

In other words, we need the set ${\cal B} := \{B_i \mid i \in I \}$ for the definition of the family $\big( B_i \big)_{i \in I}$. In general, the existence of such a set ${\cal B}$ will not follow from the axioms of Zermelo and Fraenkel introduced so far (for more details see Remark [#nst-rem-list-of-axioms]).

The solution of this problem is to introduce a further axiom, namely the axiom of substitution which guarantees the existence of the set ${\cal B}$. For more details see Section Families and the Axiom of Substitution.

Unions and Intersections of Families:

Let $\big( A_i \big)_{i \in I}$ be a family of sets, and let ${\cal A} := \{ A_i \mid i \in I \}$. We set

$$
\bigcup_{i \in I} A_i := \bigcup_{A \in {\cal A}} A \mbox{ and } \bigcap_{i \in I} A_i := \bigcap_{A \in {\cal A}} A.
$$

There are various rules to combine unions, intersections and direct products of families of sets: We have

\begin{eqnarray*}
\big( \bigcup_{i \in I} A_i \big) \cap \big( \bigcup_{j \in J} B_j \big) & = & \bigcup_{(i, j) \in I \times J} (A_i \cap B_j) \mbox{ and} \\
\big( \bigcap_{i \in I} A_i \big) \cup \big( \bigcap_{j \in J} B_j \big) & = & \bigcap_{(i, j) \in I \times J} (A_i \cup B_j).
\end{eqnarray*}

See Proposition [#nst-prop-union-and-intersection-family].

We have

\begin{eqnarray*}
\big( \bigcup_{i \in I} A_i \big) \times \big( \bigcup_{j \in J} B_j \big) & = & \bigcup_{(i, j) \in I \times J} (A_i \times B_j) \mbox{ and} \\
\big( \bigcap_{i \in I} A_i \big) \times \big( \bigcap_{j \in J} B_j \big) & = & \bigcap_{(i, j) \in I \times J} (A_i \times B_j).
\end{eqnarray*}

See Proposition [#nst-prop-union-and-product-family].

If $A_i$ is a subset of a set $A$ for all elements $i$ of an index set $I$ and if $A_i^c$ denotes the complement $A \setminus A_i$ of the set $A_i$ in the set $A$, then we have

$$
\big( \bigcup_{i \in I} A_i \big)^c = \bigcap_{i \in I} A_i^c \mbox{ and } \big( \bigcap_{i \in I} A_i \big)^c = \bigcup_{i \in I} A_i^c.
$$

See Proposition [#nst-prop-union-and-complement-family].

The next question that we want to answer is the following: Suppose that we have two families $\big( A_i \big)_{i \in I}$ and $\big( B_i \big)_{i \in I}$ and functions

$$
f_i : A_i \rightarrow B_i \mbox{ for all } i \in I.
$$

Does there exist a function

$$
f : \bigcup_{i \in I} A_i \rightarrow \bigcup_{i \in I} B_i
$$

such that

$$
f(x) = f_i(x) \mbox{ for all } x \in A_i \mbox{ and all } i \in I ?
$$

Obviously, a necessary condition is that

$$
f_i(x) = f_j(x) \mbox{ for all } x \in A_i \cap A_j \mbox{ and all } i, j \in I.
$$

As we will see in Proposition [#nst-prop-union-family-functions-1], this condition is also sufficient.

The Direct Product of arbitrary many Sets:

The definition of families offers the possibility to define the direct product not only for two sets (as in Unit Unions), but for arbitrary many sets: The intuitive definition is as follows:

Let $\big( A_i \big)_{i \in I}$ be a family of sets. Set

$$
\prod_{i \in I} A_i := \big\{ (z_i)_{i \in I} \mid z_i \in A_i \mbox{ for all } i \in I \big\}.
$$

The expression $(z_i)_{i \in I}$ is a family, that is, a function $z : I \rightarrow {\cal A}$ from the index set $I$ into the set ${\cal A} := \bigcup_{i \in I} A_i$ such that

$$
z_i = z(i) \in A_i \mbox{ for all } i \in I.
$$

The direct product $\prod_{i \in I} A_i$ therefore becomes

$$
\prod_{i \in I} A_i = \{ z : I \rightarrow {\cal A} \mid z_i := z(i) \in A_i \mbox{ for all } i \in I \}.
$$

This is the content of Definition [#nst-def-direct-product-alternative].

The Axiom of Choice:

The axiom of choice looks quite innocent: Given a family $\big( A_i \big)_{i \in I}$ of non-empty sets we want to be able to choose one element $a_i$ of each set $A_i$. This requirement sounds more or less trivial, – one wonders whether we really need a proper axiom for it. Well, we do need the axiom of choice, but we will discuss the necessity of this axiom only in the unit [Well Ordered Sets – in preparation] when we will use it to prove a rather surprising result.

It remains to answer the question how the process of choosing an element $a_i$ of each set $A_i$ is formally defined: The axiom of choice reads as follows:

Let $\big( A_i \big)_{i \in I}$ be a family of non-empty sets. Then the product

$$
\prod_{i \in I} A_i
$$

is also non-empty.

An element $(a_i)_{i \in I}$ of the product $\prod_{i \in I} A_i$ fulfills the requirement

$$
a_i \in A_i \mbox{ for all } i \in I.
$$

By definition, the element $(a_i)_{i \in I}$ is a function $f : I \rightarrow \bigcup_{i \in I} A_i$ such that

$$
f(i) = a_i \in A_i \mbox{ for all } i \in I.
$$

This function $f : I \rightarrow \bigcup_{i \in I} A_i$ is called a choice function (see Theorem [#nst-th-axiom-of-choice-variant-set] and Remark [#nst-rem-axiom-of-choice-name]).

Projections:

Let $\big( A_i \big)_{i \in I}$ be a family of non-empty sets, and let $j$ be an element of the index set $I$. The projection

$$
pr_j : \prod_{i \in I} A_i \rightarrow A_j, \: (a_i)_{i \in I} \mapsto a_j
$$

chooses the $j$th component of the element $(a_i)_{i \in I}$.

The geometric meaning of a projections is as follows:

In the affine plane

$$
A = \{ (x, y) \mid x, y \in \mathbb{R} \}
$$

the projections

\begin{eqnarray*}
pr_1 & : & A \rightarrow \mathbb{R}, \: (x, y) \mapsto x \mbox{ and} \\
pr_2 & : & A \rightarrow \mathbb{R}, \: (x, y) \mapsto y
\end{eqnarray*}

choose the first (resp. the second) coordinate of the point $p = (x, y)$.

Finally, given two families $\big( A_i \big)_{i \in I}$ and $\big( B_i \big)_{i \in I}$ we want to extend a family of functions

$$
f_i : A_i \rightarrow B_i \mbox{ for all } i \in I
$$

to a function

$$
f : \prod_{i \in I} A_i \rightarrow \prod_{i \in I} B_i.
$$

This can be done in an obvious way by setting

$$
f : (x_i)_{i \in I} \mapsto \big( f(x_i) \big)_{i \in I}.
$$

For more details see Proposition [#nst-prop-direct-products-function-bijective].

Families and the Axiom of Substitution

Functions:

Throughout this unit functions will play a crucial role. We therefore recall the definition of a function. For more details see Unit Functions.

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

(a) A function $f : A \rightarrow B$ from the set $A$ into the set $B$ is a triple $(f, A, B)$ where the set $f$ is a subset of the direct product $A \times B$ with the following property:

For each element $x$ of the set $A$, there is exactly one element $y$ of the set $B$ such that the pair $(x, y)$ is contained in the set $f$.

(b) Let $f : A \rightarrow B$ be a function from the set $A$ into the set $B$, and let $x$ be an element of the set $A$. The unique element $y$ of the set $B$ such that the pair $(x, y)$ is contained in the set $f$ is denoted by $y = f(x)$. We also write $f : x \mapsto y$ or, equivalently, $f : x \mapsto f(x)$.

Families:

Definition. An index set $I$ is a non-empty set.

French / German. Index set = Ensemble d’indices = Indexmenge.

Definition. Let $I$ be an index set, and let $A$ be a non-empty set.

(a) A function $f : I \rightarrow A$ is called a family of elements of the set $A$.

(b) Let $f : I \rightarrow A$ be a family of elements of the set $A$. We set

$$
a_i := f(i) \in A \mbox{ for all } i \in I.
$$

Instead of speaking of the family $f : I \rightarrow A$, we usually speak of the family $(a_i)_{i \in I}$ of elements of the set $A$. If we want to emphasize that the objects $a_i$ are sets, we often start with a set ${\cal A}$ of sets, then we consider a function $f : I \rightarrow {\cal A}$, and we define $A_i := f(i)$.

French / German. Family = Famille = Familie.

Remark. Note that a family $(a_i)_{i \in I}$ is only defined if there exists a set $A$ such that the element $a_i$ is contained in the set $A$ for all elements $i$ of the set $I$. Otherwise, the function $f : I \rightarrow A$ is not defined. See also the axiom of substitution and Theorem [#nst-th-substitution-existence-function].

Elementary Properties of Families:

For the proof of Theorem [#nst-th-family-identical], we will need the following elementary property of functions:

Proposition. Let $A$ and $B$ be two sets, and let $f : A \rightarrow B$ and $g : A \rightarrow B$ be two functions from the set $A$ into the set $B$.

Then we have

$$
f = g \mbox{ if and only if } f(x) = g(x) \mbox{ for all } x \in A.
$$

Theorem. Let $I$ be an index set.

Let $(x_i)_{i \in I}$ and $(y_i)_{i \in I}$ be two families of elements of a non-empty set $A$. Then we have

$$
(x_i)_{i \in I} = (y_i)_{i \in I} \mbox{ if and only if } x_i = y_i \mbox{ for all } i \in I.
$$

The Axiom of Substitution:

Remark. Let ${\cal A}$ and $B$ be two sets. We want to express something like For each set $A$ of the set ${\cal A}$, let $B_A := A \cup B$.

Unfortunately, this is in general not possible since the definition of the family $\big( B_A \big)_{ A \in {\cal A} }$ requires a function

$$
f : {\cal A} \rightarrow \{ B_A \mid A \in {\cal A} \}
$$

from the set ${\cal A}$ into the set ${\cal B} := \{ B_A \mid A \in {\cal A} \}$, but the existence of the set ${\cal B}$ is not guaranteed. The axiom of substitution solves this problem.

The axiom of substitution is one of the axioms of Zermelo and Fraenkel. The complete list of the axioms of Zermelo and Fraenkel is as follows:

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

These axioms are explained in the units Universe (ZFC-0 to ZFC-4) Unions (ZFC-5 to ZFC-7) and [Successor Sets – in preparation] (ZFC-10). The axiom of substitution (ZFC-8) and the axiom of choice (ZFC-9) are explained in the present unit.

Axiom. (ZFC-8: Axiom of Substitution or Axiom of Replacement) Let $\varphi = \varphi(x, y)$ be a sentence containing at least the two variables $x$ and $y$. (Sentences are explained in Unit Universe. They express a mathematical property such that The element $x$ is contained in the set $y$.)

Let ${\cal A}$ be a set of sets, and suppose that for each set $A$ of the set ${\cal A}$, there exists a set $B$ such that

$$
x \in B \mbox{ if and only if } \varphi(x, A).
$$

Then there exists a set ${\cal B}$ such that

$$
B \in {\cal B} \mbox{ if and only if } \: \exists \: A \in {\cal A} \mbox{ such that } \big( x \in B \Leftrightarrow \varphi(x, A) \big).
$$

French / German. Axiom of substitution (or axiom of replacement) = Axiome de substitution (or axiome de remplacement) = Ersetzungsaxiom.

Example. Let $C$ be a set, and let $\varphi = \varphi(r, S)$ be the sentence

$$
\varphi(r, S) := r \in S \cup C.
$$

Let ${\cal A}$ be a set of sets. For each set $A$ of the set ${\cal A}$, the set $B := A \cup C$ exists (axiom of unions, see Unit Unions). Note that we have

$$
x \in B \mbox{ if and only if } \varphi(x, A) \mbox{ if and only if } x \in A \cup C.
$$

By the axiom of substitution, there exists a set ${\cal B}$ such that

\begin{eqnarray*}
B \in {\cal B} & \Leftrightarrow & \exists \: A \in {\cal A} \mbox{ such that } \big( x \in B \Leftrightarrow \varphi(x, A) \big) \\
& \Leftrightarrow & \exists \: A \in {\cal A} \mbox{ such that } \big( x \in B \Leftrightarrow x \in A \cup C \big) \\
& \Leftrightarrow & \exists \: A \in {\cal A} \mbox{ such that } B = A \cup C.
\end{eqnarray*}

We are now able to define the family $\big( B_A \big)_{ A \in {\cal A} }$ via the function $f : {\cal A} \rightarrow {\cal B}$, $f : A \mapsto A \cup C$, that is,

$$
B_A := f(A) = A \cup C \mbox{ for all } A \in {\cal A}.
$$

Remark. The axiom of substitution can also be formulated as follows:

(a) A sentence $\varphi(x, y)$ in the two variables $x$ and $y$ is called functional if for each element $x$ there exists exactly one element $y$.

(b) An example for a functional sentence is $y = x \cup a$ for a given set $a$.

(c) Axiom of Substitution. For each functional sentence $\varphi = \varphi(x, y)$ and for each set $A$ there exists a set $B$ such that

$$
y \in B \mbox{ if and only if } \: \exists \: x \in A : \varphi(x, y).
$$

Theorem. Let $I$ be an index set, and let $\varphi = \varphi(x, i)$ be a sentence. Suppose that for each element $i$ of the set $I$ there exists a set $B$ such that

$$
x \in B \mbox{ if and only if } \varphi(x, i).
$$

(a) Then there exists a family $\big( B_i \big)_{i \in I}$ such that

$$
x \in B_i \mbox{ if and only if } \varphi(x, i).
$$

(b) The set ${\cal B} := \{ B_i \mid i \in I \}$ exists.

Remark. In view of Theorem [#nst-th-substitution-existence-function], we may define a family $\big( B_i \big)_{i \in I}$ directly as follows:

\begin{eqnarray*}
B_i & := & \{ x \mid \varphi(x, i) \} \mbox{ or, alternatively, by} \\
B_i & := & \psi(i)
\end{eqnarray*}

provided that for each element $i$ of the set $I$, the set $\{ x \mid \varphi(x, i) \}$ exists or that the expression $\psi(i)$ defines a set.

For example, suppose that a family $\big( A_i \big)_{i \in I}$ and a set $C$ exist, and let $\varphi(x, i) := x \in A_i \cup C$. Then we may define

$$
B_i := \{ x \mid \varphi(x, i) \} = \{ x \mid x \in A_i \cup C \} \mbox{ for all } i \in I.
$$

Setting $\psi(i) := A_i \cup C$, this definition can be abbreviated by

$$
B_i := \psi(i) = A_i \cup C \mbox{ for all } i \in I.
$$

Historical Notes:

The axiomatic of mathematics based on set theory is mainly due to Ernst Zermelo based on earlier work of Richard Dedekind and Georg Cantor. He published his first version of his axiomatic in 1908 [Zermelo-1908b]. In this article the axiom of substitution is still missing as has been noticed by Abraham Fraenkel. (Note that Fraenkel changed his given name to Abraham.)

Die überaus scharfsinnigen Untersuchungen Zermelos sollen hierdurch nicht umgestoßen, sondern nur vervollständigt und befestigt werden […]

Die sieben Zermeloschen Axiome reichen nicht aus zur Begründung der Mengenlehre.

Zum Nachweis dieser Behauptung diene etwa das folgende einfache Beispiel: Es sei $Z_0$ die in [Zermelo-1908b] definierte und als existierend nachgewiesene Menge (Zahlenreihe). Die Potenzmenge ${\cal P}(Z_0)$ (Menge aller Untermengen von $Z_0$) werde mit $Z_1$,${\cal P}(Z_1)$ mit $Z_2$ bezeichnet usw. Dann gestatten die Axiome […] nicht die Bildung der Menge $\{ Z_0, Z_1, \ldots \}$, […]

Diese bisher nicht bemerkte Lücke der Zermeloschen Begründung ist durch Hinzufügung eines neuen Axioms oder Erweiterung eines vorhandenen auszufüllen […]

Ersetzungsaxiom. Ist $M$ eine Menge und wird jedes Element von $M$ durch “ein Ding des Bereiches ${\cal B}$” (vgl. Z. S. 262) ersetzt, so geht $M$ wiederum in eine Menge über.

See [Fraenkel-1922], pp 230 – 231.

The extremely ingenious investigations of Zermelo are not meant to be overturned, but only to be completed and fortified. […]

The seven axioms of Zermelo are not sufficient to justify set theory.

The following simple example serves to prove this claim: Let $Z_0$ be the set defined in [Zermelo-1908b] and whose existence has been shown (series of numbers). Let us denote the power set ${\cal P}(Z_0)$ (set of all subsets of $Z_0$) by $Z_1$ the set ${\cal P}(Z_1)$ by $Z_2$ etc. Then the axioms […] do not allow the formation of the set $\{Z_0, Z_1, \ldots \}$, […] This hitherto undetected gap in Zermelo’s reasoning has to be filled in by adding a new axiom or expanding an existing one.

Axiom of Substitution. If $M$ is a set and every element of $M$ is replaced by “a thing of the domain ${\cal B}$” (see Z. p. 262), then $M$ turns into a set.

(Translation by the author.)

The domain ${\cal B}$ is the mathematical universe (see Unit Universe).

Zermelo published a second version of his axiomatic which is today called the axiomatic ZFC of Zermelo and Fraenkel (the letter C stands for the axiom of choice) in 1930 [Zermelo-1930]. He included the axiom of substitution in this article:

E) Axiom der Ersetzung: Ersetzt man die Elemente $x$ einer Menge $m$ eindeutig durch beliebige Elemente $x’$ des Bereiches, so enthält dieser auch eine Menge $m’$, welche alle diese $x’$ zu Elementen hat.

See [Zermelo-1930], pp. 30 – 31.

E) Axiom of Substitution: If the elements $x$ of a set $m$ are uniquely replaced by any elements $x $ of the domain, the domain also contains a set $m’$, which has all these $x’$ as elements.

(Translation by the author.)

Unions and Intersections of Families

Unions and Intersections:

Definition. Let $I$ be an index set, let $\big( A_i \big)_{i \in I}$ be a family of sets, and let ${\cal A} := \{ A_i \mid i \in I \}$. We set

$$
\bigcup_{i \in I} A_i := \bigcup_{A \in {\cal A}} A \mbox{ and } \bigcap_{i \in I} A_i := \bigcap_{A \in {\cal A}} A.
$$

Remark. Note that, by Definition, an index set is always non-empty. It follows that the set ${\cal A} := \{ A_i \mid i \in I \}$ is also non-empty. As a consequence the set $\bigcap_{A \in {\cal A}} A$ is defined.

Proposition. Let $I$ be an index set, and let $(A_i)_{i \in I}$ be a family of sets.

(a) We have

$$
x \in \bigcup_{i \in I} A_i \mbox{ if and only if } x \in A_j \mbox{ for at least one element } j \in I.
$$

(b) We have

$$
x \in \bigcap_{i \in I} A_i \mbox{ if and only if } x \in A_i \mbox{ for all } i \in I.
$$

Proposition. Let $I$ be an index set, and let $(A_i)_{i \in I}$ be a family of sets.

(a) Let $J$ be a subset of the set $I$. Then we have

$$
\bigcup_{j \in J} A_j \subseteq \bigcup_{i \in I} A_i.
$$

(b) Let $J$ be a non-empty subset of the set $I$. Then we have

$$
\bigcap_{j \in J} A_j \supseteq \bigcap_{i \in I} A_i.
$$

(c) Let $A$ and $B$ be two sets such that $A \subseteq A_i \subseteq B$ for all elements $i$ of the set $I$. Then we have

$$
A \subseteq \bigcup_{i \in I} A_i \subseteq B \mbox{ and } A \subseteq \bigcap_{i \in I} A_i \subseteq B.
$$

(d) Let $(B_i)_{i \in I}$ be a family of sets such that $A_i \subseteq B_i$ for all elements $i$ of the set $I$. Then we have

$$
\bigcup_{i \in I} A_i \subseteq \bigcup_{i \in I} B_i \mbox{ and } \bigcap_{i \in I} A_i \subseteq \bigcap_{i \in I} B_i.
$$

Proposition. Let $I$ and $J$ be two index sets, and let $I = \bigcup_{j \in J} I_j$ for a family $(I_j)_{j \in J}$ of non-empty subsets of the set $I$. Then we have

$$
\bigcup_{i \in I} A_i = \bigcup_{j \in J} \big( \bigcup_{k \in I_j} A_k \big) \mbox{ and } \bigcap_{i \in I} A_i = \bigcap_{j \in J} \big( \bigcap_{k \in I_j} A_k \big).
$$

Remark. Proposition [#nst-prop-union-of-unions-family] generalizes the associative laws

$$
(A \cup B) \cup C = A \cup (B \cup C) \mbox{ and } (A \cap B) \cap C = A \cap (B \cap C)
$$

introduced in Unit Unions.

Proposition. Let $I$ be an index set, and let $(A_i)_{i \in I}$ be a family of sets.

(a) We have

$$
A \cap \big( \bigcup_{i \in I} A_i \big) = \bigcup_{i \in I} (A \cap A_i).
$$

(b) We have

$$
A \cup \big( \bigcap_{i \in I} A_i \big) = \bigcap_{i \in I} (A \cup A_i).
$$

Proposition. Let $I$ and $J$ be two index sets, and let $(A_i)_{i \in I}$ and $(B_j)_{j \in J}$ be two families of sets.

(a) We have

$$
\big( \bigcup_{i \in I} A_i \big) \cap \big( \bigcup_{j \in J} B_j \big) = \bigcup_{(i, j) \in I \times J} (A_i \cap B_j).
$$

(b) We have

$$
\big( \bigcap_{i \in I} A_i \big) \cup \big( \bigcap_{j \in J} B_j \big) = \bigcap_{(i, j) \in I \times J} (A_i \cup B_j).
$$

Unions, Intersections and Direct Products:

Proposition. Let $I$ and $J$ be two index sets, and let $(A_i)_{i \in I}$ and $(B_j)_{j \in J}$ be two families of sets.

(a) We have

$$
\big( \bigcup_{i \in I} A_i \big) \times \big( \bigcup_{j \in J} B_j \big) = \bigcup_{(i, j) \in I \times J} (A_i \times B_j).
$$

(b) We have

$$
\big( \bigcap_{i \in I} A_i \big) \times \big( \bigcap_{j \in J} B_j \big) = \bigcap_{(i, j) \in I \times J} (A_i \times B_j).
$$

Unions, Intersections and Complements:

Proposition. Let $I$ be an index set, let $A$ be a set, and let $(A_i)_{i \in I}$ be a family of subsets of the set $A$. For a subset $X$ of the set $A$ denote by $X^c := A \setminus X$ the complement of the set $X$ in the set $A$.

(a) We have

$$
\big( \bigcup_{i \in I} A_i \big)^c = \bigcap_{i \in I} A_i^c.
$$

(b) We have

$$
\big( \bigcap_{i \in I} A_i \big)^c = \bigcup_{i \in I} A_i^c.
$$

Remark. Note that Proposition [#nst-prop-union-and-complement-family] generalizes de Morgan’s laws explained in Unit Unions.

Unions, Intersections and Inverse Images:

Proposition. Let $I$ be an index set, let $A$ and $B$ be two sets, and let $(B_i)_{i \in I}$ a family of subsets of the set $B$. Let $f : A \rightarrow B$ be a function from the set $A$ into a set $B$. Then we have

$$
f^{-1} \big( \bigcup_{i \in I} B_i \big) = \bigcup_{i \in I} f^{-1}(B_i) \mbox{ and } f^{-1} \big( \bigcap_{i \in I} B_i \big) = \bigcap_{i \in I} f^{-1}(B_i).
$$

Extensions of Functions:

Proposition. Let $I$ be an index set, and let $(A_i)_{i \in I}$ and $(B_i)_{i \in I}$ be two families of non-empty sets. For each element $i$ of the set $I$ let $f_i : A_i \rightarrow B_i$ be a function from the set $A_i$ into the set $B_i$.

Suppose that for each two elements $i$ and $j$ of the set $I$, we have $f_i(x) = f_j(x)$ for all elements $x$ of the set $A_i \cap A_j$. (Note that this implies that $f_i(x) = f_j(x) \in B_i \cap B_j$ for all $x \in A_i \cap A_j$.)

(a) There exists a function

$$
f : \bigcup_{i \in I} A_i \rightarrow \bigcup_{i \in I} B_i
$$

such that $f|_{A_i} = f_i$ for all elements $i$ of the set $I$.

(b) If the functions $f_i : A_i \rightarrow B_i$ are surjective for all elements $i$ of the set $I$, then the function $f : \bigcup_{i \in I} A_i \rightarrow \bigcup_{i \in I} B_i$ is also surjective.

Proposition. Let $I$ be an index set, let $(A_i)_{i \in I}$ and $(B_i)_{i \in I}$ be two families of non-empty sets, and suppose that the sets $(A_i)_{i \in I}$ and the sets $(B_i)_{i \in I}$ are pairwise disjoint. For each element $i$ of the set $I$ let $f_i : A_i \rightarrow B_i$ be a function from the set $A_i$ into the set $B_i$.

(a) There exists a function

$$
f : \bigcup_{i \in I} A_i \rightarrow \bigcup_{i \in I} B_i
$$

such that

$$
f(x) = f_i(x) \mbox{ for all } x \in A_i \mbox{ and for all } i \in I.
$$

(b) If the functions $f_i : A_i \rightarrow B_i$ are injective for all elements $i$ of the set $I$, then the function $f : \bigcup_{i \in I} A_i \rightarrow \bigcup_{i \in I} B_i$ is also injective.

(c) If the functions $f_i : A_i \rightarrow B_i$ are surjective for all elements $i$ of the set $I$, then the function $f : \bigcup_{i \in I} A_i \rightarrow \bigcup_{i \in I} B_i$ is also surjective.

(d) If the functions $f_i : A_i \rightarrow B_i$ are bijective for all elements $i$ of the set $I$, then the function $f : \bigcup_{i \in I} A_i \rightarrow \bigcup_{i \in I} B_i$ is also bijective.

The Direct Product of arbitrary many Sets

An Alternative Description of the Direct Product of two Sets:

We recall the definition of the direct product of two sets explained in Union Direct Products:

Definition. Let $a$ and $b$ be two sets.

The ordered pair} $(a, b)$\index{$(a, b)$} is defined by $(a, b) := \big\{ \{a\}, \{a, b\} \big\}$.

Definition. Let $A$ and $B$ be two sets. Set\index{$A \times B$}

$$
A \times B := \{ x \in {\cal P} \big( {\cal P} (A \cup B) \big) \mid \exists \: a \in A \: \exists \: b \in B \mbox{ s.t. } x = (a, b) \}.
$$

(a) The set $A \times B$ is called the direct product of the sets $A$ and $B$ or, equivalently, the Cartesian product of the sets $A$ and $B$.

(b) We write $A \times B := \{ (a, b) \mid a \in A \mbox{ and } b \in B \}$ for short.

Proposition. Let $A$ and $B$ be two non-empty sets, let $I := \{A, B\}$, and let

$$
Z := \{ z : I \rightarrow A \cup B \mid z_A := z(A) \in A \mbox{ and } z_B := z(B) \in B \}
$$

be the set of the functions $z : I = \{A, B\} \rightarrow A \cup B$ such that the elements $z(A)$ and $z(B)$ are contained in the sets $A$ and $B$, respectively.

Then the mapping

$$
\gamma : Z \rightarrow A \times B; \: \gamma : z \mapsto (z_A, z_B)
$$

is a bijective mapping from the set $Z$ onto the direct product $A \times B$.

Remark. Let $A$ and $B$ be two non-empty sets, let $I := \{A, B \}$, and let

$$
Z := \{ z : I \rightarrow A \cup B \mid z_A := z(A) \in A \mbox{ and } z_B := z(B) \in B \}
$$

be the set of the functions $z : I = \{A, B\} \rightarrow A \cup B$ such that the elements $z(A)$ and $z(B)$ are contained in the sets $A$ and $B$, respectively.

Identifying the sets $Z$ and $A \times B$ (see Proposition [#nst-prop-direct-product-alternative]) we can say that the product $A \times B$ consists of the families $(z_i)_{i \in \{A, B\} }$ such that the elements $z(A)$ and $z(B)$ are contained in the sets $A$ and $B$, respectively. If we denote the family $(z_i)_{i \in \{A, B\} }$ by $(z_A, z_B)$, we get

$$
A \times B = \{ (z_A, z_B) \mid z_A \in A \mbox{ and } z_B \in B \}.
$$

We will use this alternative definition of a direct product of two sets as a template for defining the direct product of arbitrary many sets.

Definition. Let $I$ be an index set, and let $(A_i)_{i \in I}$ be a family of sets.

(a) The direct product $A$ of the sets $A_i$ is defined as follows:

\begin{eqnarray*}
A & := & \big\{ z : I \rightarrow \bigcup_{i \in I} A_i \mid z_i := z(i) \in A_i \mbox{ for all } i \in I \big\} \\
& = & \big\{ (z_i)_{i \in I} \mid z_i \in A_i \mbox{ for all } i \in I \big\}.
\end{eqnarray*}

(b) The direct product $A$ of the sets $A_i$ is denoted by

$$
A := \prod_{i \in I} A_i.
$$

French / German. Direct product = Produit direct = Direktes Produkt.

Remark. The definition of the direct product has the little disadvantage that the direct product of two sets is defined in two different ways. On the one hand we have the definition

$$
A \times B = \{(a, b) \mid a \in A, b \in B \}
$$

according to Definition [#nst-def-ordered-pair]. On the other hand, we have Definition [#nst-def-direct-product-alternative]. Of course, it would have been possible to call the first variant the weak direct product and the second variant the direct product, but traditionally both variants are called the direct product and are used simultaneously.

Elementary Properties of the Direct Product:

Proposition. Let $I$ be an index set, let $(A_i)_{i \in I}$ be a family of sets, and let $a = \big( a_i \big)_{i \in I}$ and $b = \big( b_i \big)_{i \in I}$ be two elements of the set $A := \prod_{i \in I} A_i$. Then we have

$$
a = b \mbox{ if and only if } a_i = b_i \mbox{ for all } i \in I.
$$

Proposition. Let $I$ be an index set, let $(A_i)_{i \in I}$ be a family of sets, and let $A := \prod_{i \in I} A_i$ be the direct product of the sets $A_i$.

If $A_j = \emptyset$ for at least one element $j$ of the set $I$, then we have $A = \emptyset$.

Remark. The converse (If the sets $A_i$ are non-empty for all elements $i$ of the set $I$, then the direct product $A$ is also non-empty) will be introduced as a further axiom, the so-called axiom of choice.

The Axiom of Choice

The Axiom of Choice:

Axiom. (ZFC-9: The Axiom of Choice) Let $I$ be an index set, and let $(X_i)_{i \in I}$ be a family of non-empty sets. Then the direct product

$$
X := \prod_{i \in I} X_i
$$

is also a non-empty set.

French / German. Axiom of choice = Axiome du choix = Auswahlaxiom.

Elementary Conclusions from the Axiom of Choice:

Proposition. Let $I$ be an index set, and let $(X_i)_{i \in I}$ be a family of non-empty sets. Then there exists a family $(x_i)_{i \in I}$ of elements such that the element $x_i$ is contained in the set $X_i$ for all elements $i$ of the set $I$.

Theorem. Let ${\cal C}$ be a non-empty set of non-empty sets. Then there exists a function

$$
f : {\cal C} \rightarrow \bigcup_{C \in {\cal C}} C
$$

such that the element $f(X)$ is contained in the set $X$ for all elements $X$ of the set ${\cal C}$.

Remark. Theorem [#nst-th-axiom-of-choice-variant-set] motivates the name of the axiom of choice. The function

$$
f : {\cal C} \rightarrow \bigcup_{X \in {\cal C}} X
$$

chooses from each (non-empty) set $X$ of the (non-empty) set ${\cal C}$ an element $f(X)$. The function $f$ is sometimes called a choice function.

Theorem. Let $S$ be a non-empty set. Then there exists a function

$$
f : {\cal P}(S) \setminus \{ \emptyset \} \rightarrow S
$$

from the set of the non-empty subsets of the set $S$ into the set $S$ such that the element $f(X)$ is contained in the set $X$ for all non-empty subsets $X$ of the set $S$.

Historical Notes:

Ernst Zermelo used the axiom of choice in his proof of the theorem that every set can be endowed with a well ordering (for more details about well ordered sets see Unit [Well Ordered Sets – in preparation]). He explicitly points out that the proof of his theorem relies on the axiom of choice:

Der vorliegende Beweis beruht auf der Voraussetzung, dass […] es auch für eine unendliche Gesamtheit von Mengen immer Zuordnungen gibt, bei denen jeder Menge eines ihrer Elemente entspricht, oder formal ausgedrückt, dass das Produkt einer unendlichen Gesamtheit von Mengen, deren jede mindestens ein Element enthält, selbst von 0 verschieden ist.

[…]

Dieses logische Prinzip lässt sich zwar nicht auf ein noch einfacheres zurückführen, wird aber in der mathematischen Deduktion überall unbedenklich angewendet.

See [Zermelo-1904], p. 516.

The present proof rests upon the assumption that […] even for an infinite totality of sets there are always mappings that associate with every set one of its elements, or, expressed formally, that the product of an infinite totality of sets, each containing at least one element itself differs from zero.

[…]

This logical principle cannot, to be sure, be reduced to a still simpler one, but it is applied without hesitation everywhere in mathematical deductions.

See [Zermelo-1904-en], p. 141.

“Differs from 0” just means that the set is not empty. In 1908 Zermelo published his first list of axioms which contains the axiom of choice:

Um nun den Satz zu gewinnen, dass ein Produkt mehrerer Mengen nur dann verschwinden (d.h. der Nullmenge gleich sein) kann, wenn ein Faktor verschwindet, brauchen wir ein weiteres Axiom.

Axiom VI. Ist $T$ eine Menge, deren sämtliche Elemente von 0 verschiedene Mengen und untereinander elementfremd sind, so enthält ihre Vereinigung $\mathfrak{S} T$ mindestens eine Untermenge $S_1$, welche mit jedem Elemente von $T$ ein und nur ein Element gemein hat. (Axiom der Auswahl)

Man kann das Axiom auch so ausdrücken, dass man sagt, es sei immer möglich, aus jedem Elemente $M, N, R, \ldots$ von $T$ ein einzelnes Element $m, n, r, \ldots$ auszuwählen und alle diese Elemente zu einer Menge zu vereinigen.

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

In order, now, to obtain the theorem that the product of several sets can vanish (that is, be equal to the null set) only if a factor vanishes we need a further axiom.

Axiom VI. (Axiom of Choice) If $T$ is a set whose elements all are sets that are different from 0 and mutually disjoint, its union $\mathfrak{S} T$ includes at least one subset $S_1$ having one and only one element in common with each element of $T$.

We can also express this axiom by saying that ist is always possible to choose a single element from each element $M, N, R, \ldots$ of $T$ and to combine all the chosen elements $m, n, r, \ldots$ into a set $S_1$.

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

Projections

Definition of Projections:

Definition. Let $I$ be an index set, let $(A_i)_{i \in I}$ be a family of sets, and let $A := \prod_{i \in I} A_i$ be the direct product of the sets $A_i$.

(a) For an element $j$ of the set $I$, we define the function

$$
pr_j : A \rightarrow A_j \mbox{ by } pr_j : x = (x_i)_{i \in I} \mapsto x_j.
$$

The function $pr_j : A \rightarrow A_j$ is called the projection from the set $A$ onto the set $A_j$.

(b) For a subset $J$ of the set $I$, we define the function

$$
pr_J : A \rightarrow \prod_{j \in J} A_j \mbox{ by } pr_J : x = (x_i)_{i \in I} \mapsto (x_j)_{j \in J}.
$$

The function $pr_J : A \rightarrow A_j$ is called the projection from the set $A$ onto the set $\prod_{j \in J} A_j$.

French / German. Projection = Projection = Projektion.

Elementary Properties of Projections:

Proposition. Let $I$ be an index set, let $(A_i)_{i \in I}$ be a family of non-empty sets, and let $A := \prod_{i \in I} A_i$ be the direct product of the sets $A_i$.

(a) Let $j$ be an element of the set $I$. Then the projection $pr_j : A \rightarrow A_j$ is surjective.

(b) Let $J$ be a subset of the set $I$. Then the projection $pr_J : A \rightarrow \prod_{j \in J} A_j$ is surjective.

Proposition. Let $I$ and $J$ be two index sets, let $(I_j)_{j \in J}$ be a partition of the set $I$,\footnote{The family $(I_j)_{j \in J}$ is a partition of the set $I$ if we have $\bigcup_{j \in J} I_j = I$ and if $I_j \cap I_k = \emptyset$ for all elements $j$ and $k$ of the set $J$ such that $j \neq k$. For more details see Unit {\sc Direct Product} [\cite{nst-direct-product}].} and let $(A_i)_{i \in I}$ be a family of sets. Define the function

$$
p : \prod_{i \in I} A_i \rightarrow \prod_{j \in J} \big( \prod_{k \in I_J} A_k \big) \mbox{ by } p : x = (x_i)_{i \in I} \mapsto \big( pr_{I_j} (x) \big)_{j \in J}.
$$

Then the function $p : \prod_{i \in I} A_i \rightarrow \prod_{j \in J} \big( \prod_{k \in I_J} A_k \big)$ is bijective.

Extensions of Functions:

Proposition. Let $I$ be an index set, and let $\big(A_i \big)_{i \in I}$ and $\big(B_i \big)_{i \in I}$ be two families of sets. For each element $i$ of the set $I$, let $f_i : A_i \rightarrow B_i$ be a function from the set $A_i$ into the set $B_i$.

Define the function

$$
f : A := \prod_{i \in I} A_i \rightarrow B := \prod_{i \in I} B_i
$$

from the set $A$ into the set $B$ as follows:

Let $x = \big( x_i \big)_{i \in I}$ be an element of the set $A$. Set

$$
f(x) := \big( f_i(x_i) \big)_{i \in I} \in B.
$$

(a) If the functions $f_i : A_i \rightarrow B_i$ are injective for all elements $i$ of the set $I$, then the function $f : A \rightarrow B$ is injective.

(b) If the functions $f_i : A_i \rightarrow B_i$ are surjective for all elements $i$ of the set $I$, then the function $f : A \rightarrow B$ is surjective.

(c) If the functions $f_i : A_i \rightarrow B_i$ are bijective for all elements $i$ of the set $I$, then the function $f : A \rightarrow B$ is bijective.

Notes and References

We want to mention the books The axiom of choice by Thomas Jech [Jech-1973], Axiom of Choice by Horst Herrlich [Herrlich-2006] and Consequences of the Axiom of Choice by Paul Howard and Jean Rubin [Howard-Rubin-1998] which are devoted to the axiom of choice.

[Fraenkel-1922] Fraenkel, Adolf (1922). “Zu den Grundlagen der Cantor-Zermeloschen Mengenlehre”. In: Mathematische Annalen 86, pp. 230–237.

[Herrlich-2006] Herrlich, Horst (2006). Axiom of Choice. Lecture Notes in Mathematics. Heidelberg, Berlin, and New York: Springer Verlag.

[Howard-Rubin-1998] Howard, Paul and Jean Rubin (1998). Consequences of the Axiom of Choice. Providence: American Mathematical Society.

[Jech-1973] Jech, Thomas (1973). The Axiom of Choice. Amsterdam and New York: North Holland Publishing Company.

[Zermelo-1904] Zermelo, Ernst (1904). “Beweis, dass jede Menge wohlgeordnet werden kann”. In: Mathematische Annalen 59, pp. 514–516.

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

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

[Zermelo-1908b-en] —  (1967a). “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. This article is a translation of [Zermelo 1908] into English.

[Zermelo-1904-en] —  (1967b). “Proof that every set can be well-ordered”. In: From Frege to Gödel. A Source Book in Mathematical Logic, 1879 – 1931. Ed. by van Heijenoort, pp. 139–141. This article is a translation of [Zermelo 1904] into English.

Download

The pdf document is the full text including the proofs.

Change History

VersionDateChanges
1.0.0April 2020Creation