Axiom of Choice Definition (Intuitive)

Get­ting the Heavy Maths out the Way: Definitions

In­tu­itively, the ax­iom of choice states that, given a col­lec­tion of non-empty sets, there is a func­tion which se­lects a sin­gle el­e­ment from each of the sets.

More for­mally, given a set \(X\) whose el­e­ments are only non-empty sets, there is a func­tion

$$ f: X \rightarrow \bigcup_{Y \in X} Y $$
from \(X\) to the union of all the el­e­ments of \(X\) such that, for each \(Y \in X\), the image of \(Y\) un­der \(f\) is an el­e­ment of \(Y\), i.e., \(f(Y) \in Y\).

In log­i­cal no­ta­tion,

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

Ax­iom Un­nec­es­sary for Finite Col­lec­tions of Sets

For a finite set \(X\) con­tain­ing only finite non-empty sets, the ax­iom is ac­tu­ally prov­able (from the Zer­melo-Fraenkel ax­ioms of set the­ory ZF), and hence does not need to be given as an ax­iom. In fact, even for a finite col­lec­tion of pos­si­bly in­finite non-empty sets, the ax­iom of choice is prov­able (from ZF), us­ing the ax­iom of in­duc­tion. In this case, the func­tion can be ex­plic­itly de­scribed. For ex­am­ple, if the set \(X\) con­tains only three, po­ten­tially in­finite, non-empty sets \(Y_1, Y_2, Y_3\), then the fact that they are non-empty means they each con­tain at least one el­e­ment, 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 con­struc­tion is per­mit­ted by the ax­ioms ZF.

The prob­lem comes in if \(X\) con­tains an in­finite num­ber of non-empty sets. Let’s as­sume \(X\) con­tains a countable num­ber of sets \(Y_1, Y_2, Y_3, \ldots\). Then, again in­tu­itively speak­ing, we can ex­plic­itly de­scribe how \(f\) might act on finitely many of the \(Y\)s (say the first \(n\) for any nat­u­ral num­ber \(n\)), but we can­not de­scribe it on all of them at once.

To un­der­stand this prop­erly, one must un­der­stand what it means to be able to ‘de­scribe’ or ‘con­struct’ a func­tion \(f\). This is de­scribed in more de­tail in the sec­tions which fol­low. But first, a bit of back­ground on why the ax­iom of choice is in­ter­est­ing to math­e­mat­i­ci­ans.