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 \lbrace \emptyset\rbrace \to X$ such that $h(A) \in A$ for all $\emptyset \ne A \subseteq X$.

(1) implies (2): Consider the set

\[Y := \lbrace \lbrace A\rbrace \times A : \emptyset \ne A \subseteq X\rbrace\]

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

\[|C \cap (\lbrace A\rbrace \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 = \lbrace \langle A, a\rangle \in C : a \in A \land A \in \mathcal P(X) \setminus \lbrace \emptyset\rbrace \rbrace\]

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

Zermelo’s theorem.

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 \lbrace \emptyset\rbrace \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):

Overall idea: The following is just a fancy way of saying “pick some order $x _ 1 < x _ 2 < x _ 3 < \cdots$ and keep going until you’ve picked every element of $X$”. It gets a bit complicated because you have to do this transfinitely many times, so the indices actually become ordinals. You use Hartog’s theorem to guarantee that you’ll eventually stop.

Let $h : \mathcal P(X) \setminus \lbrace \emptyset\rbrace \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 \lbrace \langle \alpha, h(X \setminus \text{ran}(f _ \alpha)) \rangle\rbrace &\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 (inclusive):

• $\text{dom}(f _ \alpha) = \alpha$ (e.g. as in the $f _ 0$ case)
• $\text{ran}(f _ \beta) = X$ for some $\beta < \alpha$ (once you’ve enumerated all elements, you stop increasing)

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 as this is the least such $\beta$, $\text{dom}(f _ \beta) = \beta$ (note we only stop expanding the domain when this condition is met), 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 \lbrace \emptyset\rbrace \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$.