The Axiom of Choice | Real Analysis

A function picking one element from each set in a collection — for finite collections no axiom is needed, but for infinite ones this "picking" is itself an axiom. Pick one dot per row.

Examples & Exercises

Prove no axiom is needed for a finite family: if $X_1, \dots, X_m$ are all nonempty sets, there exists a tuple $(x_1, \dots, x_m)$ picking one element from each $X_i$ (induction on $m$ ).

X_1, \dots, X_m \ne \varnothing \ \Rightarrow\ \exists\,(x_1, \dots, x_m): x_i \in X_i

m = 3

, seed

= 1

: the three bins hold

3, 4, 5

balls, and the chosen tuple is

(2, 3, 4)

(0-based indices). With finitely many bins, this choice can be made by hand.

Show proof

For $m = 1$ : since $X_1 \ne \varnothing$ , some $x_1 \in X_1$ exists — this is just existential instantiation, not a choice. The tuple $(x_1)$ is what we want.
Inductive step: suppose a tuple $(x_1, \dots, x_m)$ has already been picked from $X_1, \dots, X_m$ ( $x_i \in X_i$ ). Since $X_{m+1} \ne \varnothing$ , some $x_{m+1} \in X_{m+1}$ exists, and $(x_1, \dots, x_m, x_{m+1})$ is a tuple for the $m+1$ sets.
Hence a tuple exists for every finite $m$ . The point: at each step we pick from a single named set — never "simultaneously" from infinitely many sets — so no choice axiom is needed. For an infinite family this induction never finishes, and that is exactly where the axiom enters.

Prove in both directions that the axiom of choice is equivalent to "every product of nonempty sets is nonempty".

\mathrm{AC} \iff \left( X_i \ne \varnothing\ \forall i \ \Rightarrow\ \prod_{i \in I} X_i \ne \varnothing \right)

m = 4

, seed

= 2

: the four bins hold

3, 5, 3, 5

balls, and the chosen tuple

(1, 1, 2, 0)

is itself an element of the product

X_1 \times X_2 \times X_3 \times X_4

Show proof

( $\Rightarrow$ ) Assume AC, and take a family $(X_i)_{i \in I}$ of nonempty sets. The axiom gives a choice function $c$ with $c(i) \in X_i$ for each $i$ . The tuple $(c(i))_{i \in I}$ is by definition an element of the product $\prod_{i \in I} X_i$ , so the product is nonempty.
( $\Leftarrow$ ) Conversely, assume every such product is nonempty. For any family $(X_i)_{i \in I}$ of nonempty sets, the product $\prod_{i \in I} X_i$ is nonempty, so it has an element $t$ . This $t$ is a tuple assigning to each $i$ some $t_i \in X_i$ — that is, a choice function itself. Hence the axiom of choice holds.

Prove in both directions that the axiom of choice is equivalent to "every surjection has a right inverse".

\mathrm{AC} \iff \left( f: X \twoheadrightarrow Y \ \Rightarrow\ \exists\, g: Y \to X,\ f(g(y)) = y \right)

m = 5

, seed

= 5

: the five bins hold

3, 4, 5, 2, 3

balls and the chosen tuple is

(1, 3, 0, 1, 0)

. Applying the proof's disjoint union to these five bins, a right inverse of the projection is exactly this tuple.

Show proof

( $\Rightarrow$ ) Take a surjection $f: X \to Y$ . For each $y \in Y$ , the fiber $f^{-1}(\{y\}) = \{x : f(x) = y\}$ is nonempty by surjectivity. Applying AC to the family $(f^{-1}(\{y\}))_{y \in Y}$ gives $g: Y \to X$ with $g(y) \in f^{-1}(\{y\})$ for each $y$ , i.e. $f(g(y)) = y$ : $g$ is a right inverse of $f$ .
( $\Leftarrow$ ) Assume every surjection has a right inverse, and take a family $(X_i)_{i \in I}$ of nonempty sets (if $I = \varnothing$ the empty function is a choice function, trivially). Form the disjoint union $X = \{(i, x) : i \in I,\ x \in X_i\}$ and the projection $\pi: X \to I$ , $\pi(i, x) = i$ . Since each $X_i$ is nonempty, $\pi$ is surjective.
A right inverse $s: I \to X$ of $\pi$ satisfies $\pi(s(i)) = i$ , so $s(i) = (i, x_i)$ for a uniquely determined $x_i \in X_i$ . The assignment $i \mapsto x_i$ is the desired choice function. Hence the axiom of choice holds.