📂Set Theory

Axiom of Choice

Axioms ¹

$$ \forall U \left( \emptyset \notin U \implies \exists f : U \to \bigcup_{X \in U \\ f(X) \in X } U \right) $$ For every set of sets $U$ that is not the empty set, there exists a selection function $f$ that selects exactly one element from each element of $U$.

Explanation

The axiom of choice guarantees the existence of a selection function $f$ that, for example, picks an element from each set in a set of sets $U$ like the following:

$$ U = \left\{ \left\{ \pi , 1/2 \right\} , \left\{ e , -42 \right\} , \left\{ 3/2, 1/7 , \sqrt{2} \right\} \right\} \\ f(X) = \begin{cases} \pi &, X = \left\{ \pi , 1/2 \right\} \\ e &, X = \left\{ e , -42 \right\} \\ \sqrt{2} &, X = \left\{ 3/2, 1/7 , \sqrt{2} \right\} \end{cases} $$ Of course, the existence of the range $f(U) = \left\{ \pi , e, \sqrt{2} \right\}$ of $f$ is also easily understood through the axiom of replacement. The real question is ‘Why isn’t this obviously something that should be an axiom?’. If you look closely at the above example, $f$ selects only irrational numbers from the given finite set, but whether such a $f$ can exist for whatever $U$ is given is entirely another story.

Consider a more difficult example: the set of real numbers $\mathbb{R}$ and $U = 2^{\mathbb{R}} \setminus \emptyset$:

• Since real numbers can always be compared in terms of order, it seems that the minimum value, $\min$, could be the selection function, but for the interval $(0,1] \in 2^{\mathbb{R}}$, there is no minimum value thus it can’t be the selection function.
• $\inf$ is $0 \notin (0,1]$, so it obviously can’t serve as a selection function.
• Interval length? There exist sets that are not intervals in $2^{\mathbb{R}}$.
• If $X$ is a finite set, selecting the closest number to $0$, and if it’s an infinite set, taking the intersection with the set of integers $\mathbb{Z}$ to select the closest number to $0$ is $g(X) = \begin{cases} \argmin_{x \in X } | x | &, |X| < \infty \\ \argmin_{x \in X \cap \mathbb{Z}} |x| &, | X | = \infty \end{cases}$? It cannot be defined for $\mathbb{R} \setminus \mathbb{Z}$.

… Even with just $U = 2^{\mathbb{R}} \setminus \emptyset$, finding a selection function is not as easy as one might think. However, the axiom of choice boldly asserts that a selection function exists, regardless of what it looks like. It is a bold logical step to assert its existence without being able to propose a specific $f$. Is the existence of a selection function really self-evident? Without the axiom, can one confidently say that a selection function exists? Of course, some readers of this post might have come up with a brilliant idea right away upon seeing $2^{\mathbb{R}} \setminus \emptyset$. But this is just one very small example in the vast world of mathematics. Even geniuses would not have the courage to find a selection function for every uniquely bizarre set presented to them. Let’s acknowledge the necessity of the axiom of choice and accept it.

Equivalence ¹

Meanwhile, the following theorems are introduced as equivalent to the axiom of choice.

• [1] Hausdorff’s Maximal Principle: For a partially ordered set $(A, \le)$, let the family of totally ordered subsets be $\mathcal{F}$. In $\mathcal{F}$, there exists a maximal element in the partially ordered set $(\mathcal{F}, \subset)$ with inclusion relation $\subset$ as the order.
• [2] Zorn’s Lemma: If a partially ordered set $(A, \le )$ has an upper bound for every chain, then there exists a maximal element in $A$.
• [3] Well-Ordering Principle: Any non-empty set can be endowed with a well-ordering.

The axiom of choice implies Hausdorff’s maximal principle, which implies Zorn’s Lemma, which implies the well-ordering principle, which implies the axiom of choice. These theorems are equivalently expressed different from the axiom of choice only in terms of their representation and applications. Saying that their uses are different simply means that the axiom of choice is used in proofs, but an equivalent that fits the proof is used instead. In particular, Zorn’s Lemma is famously frequently used as its name suggests, in various fields.