0.3 Axiom of Choice and Equivalents (Zorn's lemma, Hausdorff's maximal principle, Well ordering and Tukey's Lemma)

Now we discuss fundamental axiom of set theory - Axiom of Choice.

The following are equivalent.

1. (The Hausdorff Maximal Principle). Every partially ordered set has a maximal linearly ordered subset.
2. (Zorn's Lemma). If $X$ is partially ordered set and every linearly ordered subset of $X$ has an upper bound, then $X$ has a maximal element.
3. (Well Ordering Principle). Every nonempty set $X$ can be well ordered.
4. (Axiom of Choice). If $\left\{ X_{a} \right\}_{a \in A}$ is nonempty collection of nonempty sets, then $\prod_{a \in A} X_{a}$ is nonempty.
5. (Tukey's Lemma). Every nonempty collection of finite character partially ordered by set inclusion has a maximal element.

We will prove the equivalence by showing $$(1) \implies (2) \implies (3) \implies (4) \implies (2) \implies (5) \implies (1)$$ $(\textbf{1} \implies \textbf{2})$ Let $(X, \leq)$ be partially ordered set with the following property. $$\text{"every linearly ordered subset of }X\text{ has an upper bound"}$$ Then by $1$, there exist maximal linearly ordered subset; namely $S$. Let $m$ be an upper bound of $S$. If there exists an element $x \in X$ such that $m < x$, then $S \cup \left\{ x \right\}$ is also linearly ordered subset of $X$, contradicting to the maximality of $S$. So $m$ is the maximal element of $X$.

$(\textbf{2} \implies \textbf{3})$ Let $\mathcal{W}$ be the collection of well orderings of subsets of $X$. We define a partial ordering $\lesssim$ on $\mathcal{W}$ as follows. If $\leq_{1}$ and $\leq_{2}$ are well orderings on the subsets $E_{1}$, $E_{2}$ of $X$, then $$(\leq_{1})\ \lesssim\ (\leq_{2}) \iff \begin{cases} E_{1} \subset E_{2},\ \leq_{1}\text{ and }\leq_{2}\text{ agrees on }E_{1} \\ \text{for all } x \in E_{2} \setminus E_{1}, y \leq x\text{ for all } y \in E_{1} \end{cases}$$ Let $S = \left\{ \leq_{\alpha} \right\}_{\alpha \in \Lambda}$ be linearly ordered subset of $\mathcal{W}$, with well ordering $\leq_{\alpha}$ defined on $E_{\alpha} \subset X$.

$\leq^{\ast} = \cup_{\alpha} \leq_{\alpha}$ is a well ordering on $\cup_{\alpha} E_{\alpha}$.

Pick $x, y \in \cup_{\alpha} E_{\alpha}$. Define $$I = \left\{ E_{\alpha}: \alpha \in \Lambda,\ \left\{ x, y\right\}\subset E_{\alpha} \right\}$$ and $E = \cap I$.

• If $E$ is nonempty, pick $E_{\alpha}, E_{\beta} \in I$. By linear ordering of $S$, either $(\leq_{\alpha})\ \lesssim\ (\leq_{\beta})$ or vice versa. Either case, $$x \leq_{\alpha} y \iff x \leq_{\beta} y$$ or $$y \leq_{\alpha} x \iff y \leq_{\beta} x$$ so $\leq^{\ast}$ is well defined.
• If $E$ is empty, $x \in E_{\alpha}$, $y \in E_{\beta}$ for $\alpha \neq \beta$. But then by linear ordering of $S$, either $(\leq_{\alpha})\ \lesssim\ (\leq_{\beta})$ or vice versa, which induces inclusion relation between $E_{\alpha}$ and $E_{\beta}$. This implies either one of them includes both elements $x$ and $y$; contradiction.

Now suppose $M$ is nonempty subset of $\cup_{\alpha} E_{\alpha}$ such that has no least element. Then there exist a sequence $\left\{ x_{n} \right\} \subset X$ such that $$x_{1} {}^{\ast}> x_{2} {}^{\ast}> ... {}^{\ast}> x_{n} {}^{\ast}> x_{n+1}...$$ Now suppose $x_{1} \in E_{\alpha_{1}}$. Then we can deduce that all elements are in $E_{\alpha_{1}}$, which then ${}^{\ast}>$ reduces to $>_{\alpha_{1}}$. Since $>_{\alpha_{1}}$, it has least element, which is contradiction. So $\leq^{\ast}$ is a well ordering on $\cup_{\alpha} E_{\alpha}$.

Now back to the original proof, pick any $E_{\beta}$ and $\leq_{\beta}$ where $\beta \in \Lambda$. Clearly by definition $E_{\beta} \subset \cup_{\alpha}E_{\alpha}$ and $\leq^{\ast}$ agrees with $\leq_{\beta}$ on $E_{\beta}$. Next for $x \in \cup_{\alpha}E_{\alpha} \setminus E_{\beta}$, there exist $\gamma$ such that $x \in E_{\gamma} \setminus E_{\beta}$. By linear ordering of $S$, the only possibility is $E_{\beta} \subset E_{\gamma}$, so that $y \leq_{\gamma} x$; which in turn $y \leq^{\ast} x$ for all $y \in E_{\beta}$. This asserts that $S$ is bounded above by $\leq^{\ast}$. By Zorn's Lemma, $\mathcal{W}$ has maximal element $\leq$. If $\leq$ is well ordering on some proper subset $T$ of $X$, we can add single element $x_{0} \in X \setminus T$ and define $\leq'$ on $T \cup \left\{ x_{0} \right\}$ by $\leq'$ agrees with $\leq$ on $T$ and $t \leq' x_{0}$ for all $t \in T$. This shows the only possibility of $\leq$ is well ordering on $X$ (whole set).

$(\textbf{3} \implies \textbf{4})$ Let $X = \cup_{\alpha \in A} X_{\alpha}$, and pick a well ordering on $X$. For each $\alpha$, define $f(\alpha)$ to be a minimal element of $X_{\alpha}$. Then $f \in \prod_{\alpha \in A} X_{\alpha}$.

$(\textbf{4} \implies \textbf{2})$ Let $(X, \leq)$ be a nonempty partially ordered set with property that every linearly ordered subset has an upper bound. For each $x \in X$, define $$S_{x} = \begin{cases} \left\{ y \in X: y > x \right\} & (\text{if } x \text{ is not maximal element of } X) \\ \left\{ x \right\} & (\text{if } x \text{ is maximal element of }X) \end{cases}$$ Then by axiom of choice, $\prod_{x \in X} S_{x}$ is not empty. So we've constructed a function $f \in \prod_{x \in X} S_{x}$ such that $$f: X \rightarrow X,\ x \leq f(x)\ (\forall x \in X)$$ Now by Bourbaki's Fixed Point Theorem, there exist $x^{\ast} \in X$ such that $f(x^{\ast}) = x^{\ast}$. By definition of $S_{x^{\ast}}$, automatically $x^{\ast}$ is the maximal element of $X$ and Zorn's Lemma follows.

$(\textbf{2} \implies \textbf{5})$ Let $\mathcal{F}$ be collection of sets that is of finite character. $\subseteq$ is a natural partial ordering on $\mathcal{F}$. Let $\mathcal{C}$ be nonempty linearly ordered subset of $\mathcal{F}$.

$\bigcup \mathcal{C} \in \mathcal{F}$.

Let $M = \left\{ m_{1}, ..., m_{n} \right\}$ be a finite subset of $\cup \mathcal{C}$. Then there exist $C_{i} \in \mathcal{C}$ for each $i = 1, 2, ..., n$ such that $m_{i} \in C_{i}$. Since $\mathcal{C}$ is linearly ordered, there is a set $C_{j}$ among $C_{i}$s' such that $C_{j} \supset C_{i}$ for all $i$, so that $$M \subset C_{j}$$ Thus $M \in \mathcal{F}$ as $C_{j} \in \mathcal{F}$ and $\mathcal{F}$ is finite character. It follows that $\cup \mathcal{C} \in \mathcal{F}$.

Back to original proof, it is clear that $\cup \mathcal{C}$ is an upper bound for $\mathcal{C}$. By Zorn's Lemma, there is a maximal element of $\mathcal{F}$; which is exactly what Tukey's Lemma states.

$(\textbf{5} \implies \textbf{1})$ Let $(X, \leq)$ be a partially ordered set. Define $\mathcal{L}$ to be collection of all linearly ordered subsets of $X$.
$(\implies)$ Pick $L \in \mathcal{L}$. Any finite subset of $L$ is also linearly ordered (trivial). So any finite subset of $L$ is in $\mathcal{L}$.
$(\impliedby)$ Suppose all finite subsets of $A \subset X$ are members of $\mathcal{L}$. Then for any finite subsets of $A$ of the form $\left\{ x,y \right\}$ satisfy either $x \leq y$ or $y \leq x$. The union over all such two elements subsets, form $A$; which then makes $A$ linearly ordered. So $A \in \mathcal{L}$.
This shows $\mathcal{L}$ is of finite character, and by Tukey's Lemma there exist maximal element (which is maximal linearly ordered subset of $X$). Hausdorff's Maximal Principle directly follows.