Getting the Heavy Maths out the Way: Definitions

Intuitively, the axiom of choice states that, given a collection of non-empty sets, there is a function which selects a single element from each of the sets.

More formally, given a set $X$ whose elements are only non-empty sets, there is a function

$$ f: X \rightarrow \bigcup_{Y \in X} Y $$

from $X$ to the union of all the elements of $X$ such that, for each $Y \in X$, the image of $Y$ under $f$ is an element of $Y$, i.e., $f(Y) \in Y$.

In logical notation,

$$ \forall_X \left( \left[\forall_{Y \in X} Y \not= \emptyset \right] \Rightarrow \left[\exists \left( f: X \rightarrow \bigcup_{Y \in X} Y \right) \left(\forall_{Y \in X} \exists_{y \in Y} f(Y) = y \right) \right] \right) $$

Axiom Unnecessary for Finite Collections of Sets

For a finite set $X$ containing only finite non-empty sets, the axiom is actually provable (from the Zermelo-Fraenkel axioms of set theory ZF), and hence does not need to be given as an axiom. In fact, even for a finite collection of possibly infinite non-empty sets, the axiom of choice is provable (from ZF), using the axiom of induction. In this case, the function can be explicitly described. For example, if the set $X$ contains only three, potentially infinite, non-empty sets $Y_1, Y_2, Y_3$, then the fact that they are non-empty means they each contain at least one element, say $y_1 \in Y_1, y_2 \in Y_2, y_3 \in Y_3$. Then define $f$ by $f(Y_1) = y_1$, $f(Y_2) = y_2$ and $f(Y_3) = y_3$. This construction is permitted by the axioms ZF.

The problem comes in if $X$ contains an infinite number of non-empty sets. Let’s assume $X$ contains a countable number of sets $Y_1, Y_2, Y_3, \ldots$. Then, again intuitively speaking, we can explicitly describe how $f$ might act on finitely many of the $Y$s (say the first $n$ for any natural number $n$), but we cannot describe it on all of them at once.

To understand this properly, one must understand what it means to be able to ‘describe’ or ‘construct’ a function $f$. This is described in more detail in the sections which follow. But first, a bit of background on why the axiom of choice is interesting to mathematicians.

Axiom of Choice: Definition (Formal)

Getting the Heavy Maths out the Way: Definitions

Axiom Unnecessary for Finite Collections of Sets