Axiom of Choice

Definition. Given a set $X$, a choice function (on $X$) is a function $f : X \setminus \{\emptyset\} \to \bigcup X$ such that $f(x) \in x$ for all $x$.

Axiom of choice. Every set has a choice function.

Definition. A set of representatives $R$ for a partition $P$ of a set $X$ is a set $R \subseteq X$ such that $R \cap p$ contains one exact element for every $p \in P$.

Proposition. The following statements are equivalent.

1. Every set has a choice function.

2. Every surjective function has a right-inverse.

3. Every partition has a set of representatives

4. A product of nonempty sets is nonempty.

Proof. (1) ⇒ (2) Let $f : X \to Y$ be surjective. Let $g : Y \to \mathcal{P}(X)$ be the map $g^{-1}(y)$ and $h$ a choice function on $\mathcal{P}(X)$. Then $h \circ g$ is a right-inverse.

(2) ⇒ (3) If $P$ is a partition of $X$, then there is a well-defined function $f : X \to P$ such that $x \in f(x)$, which must be surjective. Let $g$ be its right-inverse. Then $g(P)$ is a set of representatives.

(3) ⇒ (4) Let $\{X_i\}_{i \in I}$ be any family of sets. Then $P = \{ \{i\} \times X_i \ : \ i \in I \}$ is a partition. If $R$ is a set of representatives, its elements are of the form $(i, x)$ where $x \in X_i$. So it is the graph of a function $f$ on $I$ such that $f(i) \in X_i$. Thus, $f \in \prod_{i \in I} X_i$.

(4) ⇒ (1) Given a set $X$, let $f \in \prod_{x \in X^*} x$ where $X^* = X \setminus \{\emptyset\}$. By definition, $f(x) \in x$ for all $x$. $\square$

Definition. A relation $\sim$ on $X$ is said to be total, or left-total, if for every $x$ there exists a $y$ such that $x \sim y$.

There are weaker versions of the axiom of choice. For example, the axiom of countable choice states that every countable product of nonempty sets is nonempty. The axiom of dependent choice states for every left-total relation $\sim$ on a set $X$, there exists a sequence $(x_n)$ on $X$ such that $x_n \sim x_{n+1}$ for all $n < \omega$.

Proposition. choice ⇒ dependent choice ⇒ countable choice

Proof. Let $f$ be a choice function and $\sim$ a left-total relation on $X$. Via induction, let $x_0 \in X$ be any element, and $x_{n+1} = f(\{ y \in X \ : \ x_n \sim y \})$. Then the sequence $(x_n)$ is the one we wish (we need left-totality since $f$ is not defined for the empty set).

Let $X = \{X_n\}_{n < \omega}$ be countable with each $X_n \ne \emptyset$. Let $Y = \{ (n, x) \ : \ x \in X_n \}$. Define the relation $\sim$ on $Y$ such that $(n, x) \sim (m, y) \iff n + 1 = m$. This is left-total since every $X_{n+1}$ is nonempty for all $n$, so let $(y_n)$ be the sequence in $Y$ with $y_n \sim y_{n+1}$. It’s easily shown by induction that for each $n$, $y_n = (n, x)$ for some $x \in X_n$ so that the second coordinate of $(y_n)$ gives us a sequence $s = (x_n)$ such that $s \in \prod_{n < \omega} X_n$. $\square$