Families and the Axiom of Choice

1 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 2.3 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 3.2 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 5.2 about the existence of a choice function.

---

---

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

---

---

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

---

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

---

---

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

---

---

---

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

---

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

---

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.

---

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

---

---

4 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:

---

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

---

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

---

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

---

---

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

---

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

is also a non-empty set.

---

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

---

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

---

---

6 Projections

Projections are an important tool in geometry. At this point we restrict ourselves to give the formal definition of a projection:

---

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

---

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

---

---

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

---

---

8 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