Set Theory HT25, Choice



Flashcards

@State the axiom of 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$.

Choice functions

@State an equivalent formulation of the axiom of choice in terms of choice functions.


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

@Prove that the following are equivalent:

  1. The axiom of choice, i.e. that if $X$ is a set of disjoint non-empty sets, then there exists a set $C$ such that $ \vert C \cap a \vert = 1$ for all $a \in X$.
  2. 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.

Well-ordering principle

@State an equivalent formulation of the axiom of choice in terms of well-orders.


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

@State Zermelo’s theorem.


The axiom of choice implies the well-ordering principle.

What’s another name for the theorem that the axiom of choice implies the well-ordering principle?


Zermelo’s theorem.

@Prove that the following are equivalent:

  1. The axiom of choice, i.e. that if $X$ is a set of disjoint non-empty sets, then there exists a set $C$ such that $ \vert C \cap a \vert = 1$ for all $a \in X$.
  2. Every set can be well-ordered, i.e. for every $X$ there exists some $<$ such that $(X, <)$ is a well-order.

You may use alternative characterisations of the axiom of choice.


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.

Cardinal comparability

@State an equivalent formulation of the axiom of choice in terms of cardinal comparability.


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

@Prove that the following are equivalent:

  1. The axiom of choice, i.e. that if $X$ is a set of disjoint non-empty sets, then there exists a set $C$ such that $ \vert C \cap a \vert = 1$ for all $a \in X$.
  2. 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 $.

You may use alternative characterisations of the axiom of choice.


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

Zorn’s lemma

The axiom of choice is also equivalent to Zorn’s lemma, i.e. that if $(X, <)$ is a partially ordered set in which every chain has an upper bound, then $(X, <)$ has a maximal element. See [[Notes - Set Theory HT25, Zorn’s lemma]]U.




Related posts