Axiom of Choice Definition (Intuitive)

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.