# Axiom of Choice, Zorn's Lemma, Well-ordering Theorem

###### tags: `Set Theory`

## Axiom of Choice

:::info
$\forall \mathscr A \colon \bigl( \varnothing \notin \mathscr A \implies \exists f \in \mathscr A \to \bigcup \mathscr A, \forall X \in \mathscr A \colon f(X) \in X \bigr)$
:::

## Zorn's Lemma

:::info
A partially ordered set $(X, \leq)$ containing upper bounds for every chain (that is, every totally ordered subset) necessarily contains at least one maximal element.
:::

### Axiom of Choice $\implies$ Zorn's Lemma

:::info
* Ref: https://digitalcommons.kennesaw.edu/cgi/viewcontent.cgi?article=2161&context=facpubs
* [Simpler Proof of Zorn’s Lemma](/B19cNHw1L)
:::

### Zorn's Lemma $\implies$ Axiom of Choice

:::success
* $\forall \mathscr A \colon \bigl( \varnothing \notin \mathscr A \implies \bigr)$
* $\mathscr J \equiv \bigl\{ g \subseteq \mathscr A \times \bigcup \mathscr A \bigm| g \in \mathrm{dom}(g) \to \bigcup \mathscr A \land \bigl( \forall X \in \mathrm{dom}(g) \colon g(X) \in X \bigr) \bigr\}$
* $(\mathscr J, \subseteq)$ is partial ordered
:::

:::info
$\forall \mathscr K \in \mathrm{TO}(\mathscr J, \subseteq), \exists g \in \mathscr J, \forall h \in \mathscr K \colon h \subseteq g$
:::

:::warning
* $\forall \mathscr K \in \mathrm{TO}(\mathscr J, \subseteq)$
* Let $g = \bigcup \mathscr K$
* $\forall X \in \mathrm{dom}(g)$
* $\because X \in \mathrm{dom}(g) \therefore \exists y \colon Xgy$
* $\because Xgy \land g = \bigcup \mathscr K \therefore \exists u \in \mathscr K \subseteq \mathscr J \colon X \in \mathrm{dom}(u) \land u(X) = y$
* $\because u \in \mathscr J \therefore y = u(X) \in X$
* $(1) \colon \forall z \colon (Xgz \implies )$
* $\because Xgz \land g = \bigcup \mathscr K \therefore \exists v \in \mathscr K \colon X \in \mathrm{dom}(v) \land v(X) = z$
* $\because u, v \in \mathscr K \in \mathrm{TO}(\mathscr J, \subseteq) \therefore u \subseteq v \lor v \subseteq u$
* $u \subseteq v \implies$
* $\because u \subseteq v \land X \in \mathrm{dom}(u) \therefore y = u(X) = v(X) = z$
* $v \subseteq u \implies$
* $\because v \subseteq u \land X \in \mathrm{dom}(v) \therefore z = v(X) = u(X) = y$
* $(*) \colon y = z$
* $\because Xgy \land (1 \colon *) \land y \in X \therefore \exists! y \in X \colon Xgy$
* $\forall X \in \mathrm{dom}(g) \subseteq \mathscr A \colon \exists! y \in X \subseteq \bigcup \mathscr A \colon Xgy$
* $(2) \colon g \in \mathrm{dom}(g) \to \bigcup \mathscr A$
* $(3) \colon \forall X \in \mathrm{dom}(g)$
* $\exists! y \in X \colon g(X) = y$
* $(*) \colon g(X) \in X$
* $\because (2) \land (3 \colon *) \therefore g \in \mathscr J$
* $\forall h \in \mathscr K \colon h \subseteq \bigcup \mathscr K = g$
* $\exists g = \bigcup \mathscr K \in \mathscr J, \forall h \in \mathscr K \colon h \subseteq g$
:::

:::info
(Zorn's Lemma): $\exists f \in \mathscr J, \forall g \in \mathscr J \colon f \not \subset g$
:::

:::info
$f \in \mathscr A \to \bigcup \mathscr A \land \bigl( \forall X \in \mathscr A \colon f(X) \in X \bigr)$
:::

:::warning
* $\forall X \in \mathscr A$
* $\because X \in \mathscr A \land \varnothing \notin \mathscr A \therefore X \neq \varnothing$
* $\exists p \colon p \in X \subseteq \bigcup \mathscr A$
* $Xfp \implies X \in \mathrm{dom}(f)$
* $\lnot Xfp \implies$
* Let $g = f \cup \{\left<X, p\right>\}$
* $\because \lnot Xfp \therefore f \subset g$
* $g \notin \mathscr J$
* $\because Xgp \land p \in X \land g \notin \mathscr J \therefore g \notin \mathrm{dom}(g) \to \bigcup \mathscr A$
* $\exists Y, q, r \colon Ygq \land Ygr \land q \neq r$
* $\because Ygq \land g = f \cup \{\left<X, p\right>\} \therefore Y \in \mathrm{dom}(f) \land f(Y) = q \lor \left<Y, q\right> = \left<X, p\right>$
* $Y \in \mathrm{dom}(f) \land f(Y) = q \implies$
* $f(Y) = q \neq r$
* $\because Ygr \land f(Y) \neq r \therefore \left<Y, r\right> = \left<X, p\right>$
* $X = Y \in \mathrm{dom}(f)$
* $\left<Y, q\right> = \left<X, p\right> \implies$
* $Y = X \land p = q \neq r$
* $\left<Y, r\right> \notin \{\left<X, p\right>\}$
* $\because Ygr \land \left<Y, r\right> \notin \{\left<X, p\right>\} \therefore Y \in \mathrm{dom}(f) \land f(Y) = r$
* $X = Y \in \mathrm{dom}(f)$
* $\because \mathrm{dom}(f) \subseteq \mathscr A \land \bigl( \forall X \in \mathscr A \colon X \in \mathrm{dom}(f) \bigr) \therefore \mathrm{dom}(f) = \mathscr A$
* $\because f \in \mathscr J \land \mathrm{dom}(f) = \mathscr A \therefore f \in \mathscr A \to \bigcup \mathscr A \land \bigl( \forall X \in \mathscr A \colon f(X) \in X \bigr)$
:::