Families and the Axiom of Choice
- Introduction
- Families and the Axiom of Substitution
- Unions and Intersections of Families
- The Direct Product of arbitrary many Sets
- The Axiom of Choice
- Projections
- Notes and References
- Download
Introduction
In the following you will find a short summary of this unit. For detailed information please see the full text or download the pdf-document at the end of this page.
The present unit is the fifth unit of the walk The Axioms of Zermelo and Fraenkel. On the one hand we will introduce the formal definition of a family $(A_i)_{i \in I}$ within the framework of the axiomatics Zermelo and Fraenkel. On the other hand we will add the axiom of substitution and the axiom of choice to the series of axioms introduced so far:
We will explain the following axioms of Zermelo and Fraenkel:
- ZFC-8: The Axiom of Substitution
- ZFC-9: The Axiom of Choice
You will learn the meaning of the following terms:
- Index Set
- Family of Elements or Family of Sets
- Functional Sentence
- Union of a Family of Sets
- Intersection of a Family of Sets
- Direct Product of arbitrary many Sets
- Choice Function
- Projection
The main results of this unit are
- Theorem [#nst-th-family-identical] saying that two families $(A_i)_{i \in I}$ and $(B_i)_{i \in I}$ are equal if and only if we have $A_i = B_i$ for all elements $i$ of the index set $I$,
- Proposition [#nst-prop-union-family-functions-1] about the possibility to extend functions $f_i : A_i \rightarrow B_i$ to a common function $f : \bigcup_{i \in I} A_i \rightarrow \bigcup_{i \in I} B_i$,
- Theorem [#nst-th-axiom-of-choice-variant-set] about the existence of a choice function.
Families and the Axiom of Substitution
We will explain how to define a family of sets within the framework of Zermelo and Fraenkel. What is important is the axiom of substitution which offers a lot of freedom in defining 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.
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.
$$
Definition. 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$.
French / German. Functional Sentence = Terme Fonctionel = Funktionaler Ausdruck.
Axiom. (ZFC-8: Axiom of Substitution or Axiom of Replacement) 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).
$$
French / German. Axiom of substitution (or axiom of replacement) = Axiome de substitution (or axiome de remplacement) = Ersetzungsaxiom.
Theorem. Let $I$ be an index set, let $\varphi = \varphi(i)$ be a sentence, and suppose that the sentence $\psi(i, A) := [A = \varphi(i)]$ is functional. Then the family $(A_i)_{i \in I}$ with $A_i := \varphi(i)$ exists.
Unions and Intersections of Families
After the introduction of families we are now going to define the union $\bigcup_{i \in I} A_i$ and the intersection $\bigcap_{i \in I} A_i$ of a family $(A_i)_{i \in I}$ of sets. The most important results concern the extension of functions $f : A_i \rightarrow B_i$ to a common function $f : \bigcup_{i \in I} A_i \rightarrow \bigcup_{i \in I} B_i$.
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.
$$
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
In this section we will extend the definition of the direct product of two sets explained in Unit Direct Products and Relations to 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.
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$.
The Axiom of Choice
In this section we will explain the axiom of choice: Given a family of non-empty sets $(A_i)_{i \in I}$ it allows to define a so-called choice function $f : I \rightarrow \bigcup_{i \in I} A_i$ such that the element $f(i)$ is contained in the set $A_i$ for all elements $i$ of the set $I$.
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.
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.
Projections
Projections are an important tool in geometry. At this point we restrict ourselves to give the formal definition of a projection:
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.
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.
Notes and References
A list of textbooks about set theory is contained in Unit [Literature about Set Theory].
Do you want to learn more? The next unit, Ordered Sets and the Lemma of Zorn, explains ordered sets. The most important result of this unit is the Lemma of Zorn about the existence of maximal elements in a (partially) ordered set. It follows from the axiom of choice.
Download
Families and the Axiom of Choice
The pdf document is the full text including the proofs.
Current Version: 1.0.3 from October 2020