---
# System prepended metadata

title: 'Axiom of Choice, Zorn''s Lemma, Well-ordering Theorem'
tags: [Set Theory]

---

# 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)$
:::
