Notes - Set Theory HT25, Choice

If $X$ is a set of disjoint non-empty sets, then there exists a set $C$ such that

\[|C \cap a| = 1\]

for all $a \in X$.

Every set $X$ has a choice function, a function $h : \mathcal P(X) \setminus \{\emptyset\} \to X$ such that $h(A) \in A$ for all $\emptyset \ne A \subseteq X$.

(1) implies (2): Consider the set

\[Y := \\{\\{A\\} \times A : \emptyset \ne A \subseteq X}\]

Then $Y$ is a set of disjoint non-empty sets, so let $C$ be such that

\[|C \cap (\\{A\\} \times A)| = 1\]

for all $A \subseteq X$ non-empty. Then for each $A$, there is precisely one $a$ such that $a \in A$ and $\langle A, a \rangle \in C$, so setting $h(A) := a$ defines a choice function. Explicitly,

\[h = \\{\langle A, a\rangle \in C : a \in A \land A \in \mathcal P(X) \setminus \\{\emptyset\\}\\}\]

(2) implies (1): If $X$ is a set of disjoint non-empty sets and $h$ is a choice function for $\bigcup X$, then $C := h[X]$ is as required.

Every set can be well-ordered, i.e. for every $X$ there exists some $<$ such that $(X, <)$ is a well-order.

The axiom of choice implies the well-ordering principle.

First, we know that the axiom of choice is equivalent to the statement that:

1. Every set $X$ has a choice function, a function $h : \mathcal P(X) \setminus \{\emptyset\} \to X$ such that $h(A) \in A$ for all $\emptyset \ne A \subseteq X$.

so it suffices to prove that this is equivalent to (2).

(1) implies (2) (Zermelo’s theorem):

Let $h : \mathcal P(X) \setminus \{\emptyset\} \to X$ be a choice function. By the transfinite recursion theorem, we may define a chain of injections $(f _ \alpha) _ {\alpha \in \mathbf{ON}}$ from ordinals to $X$ such that:

• $f _ 0 = \emptyset$
• $f _ {\alpha^+} = \begin{cases} f _ \alpha \cup \{\langle \alpha, h(X \setminus \text{ran}(f _ \alpha)) \rangle\} &\text{if } X \setminus \text{ran}(f _ \alpha) \ne \emptyset \\ f _ \alpha &\text{otherwise} \end{cases}$
• $f _ \eta = \bigcup _ {\beta \in \eta} f _ \beta$ for $\eta$ a limit ordinal

Then by transfinite induction, for all $\alpha \in \mathbf{ON}$ either $\text{dom}(f _ \alpha) = \alpha$, or $\text{ran}(f _ \beta) = X$ for some $\beta < \alpha$.

Recall Hartog’s theorem:

If:

• $X$ is a set

Then:

• There exists $\alpha \in \mathbf{ON}$ with $ \vert \alpha \vert \not\le \vert X \vert $.

By Hartog’s theorem, the second case must occur for some $\alpha \in \mathbf{ON}$, so let $\beta \in \mathbf{ON}$ be least such that $\text{ran}(f _ \beta) = X$, which exists by the result which says the class relation $\in$ on $\mathbf{ON}$ is a well-order and so every non-empty subclass has a least element.

Then $\text{dom}(f _ \beta) = \beta$, so $f _ \beta : \beta \to X$ is a bijection and then it follows that $X$ is well-ordered by the result that says a set is well-ordered iff it is equinumerous with an ordinal.

(2) implies (1):

Let $X$ be a set. By the well-ordering principle, $X$ can be well-ordered, and then

\[\min : \mathcal P(X) \setminus \\{\emptyset\\} \to X\]

is a choice function.

The order $<$ on cardinalities is total, i.e. for two sets $X$ and $Y$, either $ \vert X \vert \le \vert Y \vert $ or $ \vert Y \vert \le \vert X \vert $.

First, we know that the axiom of choice is equivalent to the statement that:

1. Every set can be well-ordered, i.e. for every $X$ there exists some $<$ such that $(X, <)$ is a well-order.

so it suffices to prove that this is equivalent to (2).

(1) implies (2):

By the result which says

Suppose $(X, <)$ and $(Y, <’)$ are well-orders, then either $(X, <)$ is isomorphic to an initial segment of $(Y, <’)$ or $(Y, <’)$ is isomorphic to an initial segment of $(X, <)$.

we can always compare well-orders; if sets $X$ and $Y$ can be well-ordered, then one admits an injection to the other.

(2) implies (1):

Let $X$ be a set. By Hartog’s theorem, we know that there exists some $\alpha \in \mathbf{ON}$ with $ \vert \alpha \vert \not\le \vert X \vert $. By cardinal comparability, $ \vert X \vert \le \vert \alpha \vert $, so there exists an injection $f : X \to \alpha$, and then $x < y \iff f(x) \in f(y)$ defines a well-order on $X$.