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

Children:

Parents: