---
tag: T143XYG84N
kind: proof
name: Proof of Zorn's lemma from the axiom of choice by good chains
msc: ["03E25"]
proves: 04RXTQA5ZA
uses: [0HTGB13FE2, 0YXEQWRGP0, 011C29Q1S1, 0GP9ASVQ1X, 0H5J02P8S9, 0TZEEFTNCC]
sources:
  - url: https://arxiv.org/abs/2404.11638
    locator: Appendix A
---

## Proof

We argue by contradiction. Let $(P, \le)$ be a nonempty [[partially ordered set|011C29Q1S1]] in which each [[chain|0GP9ASVQ1X]] has an [[upper bound|0H5J02P8S9]]. Write $x < y$ for $x \le y$ and $x \neq y$.

1. Suppose that $P$ has no [[maximal element|0TZEEFTNCC]]. For a chain $C$, let $S(C) = \{p \in P : c < p \text{ for all } c \in C\}$, the set of strict upper bounds of $C$.
2. Each $S(C)$ is nonempty. Let $u$ be an upper bound of $C$. Since $u$ is not maximal, some $v \in P$ has $u < v$.
3. For $c \in C$ we have $c \le u < v$, so $c \le v$. If $c = v$, then $v \le u \le v$ and $u = v$, which is false. So $c < v$, and $v \in S(C)$.
4. The sets $S(C)$, for all chains $C$, form a set of nonempty sets. By the [[axiom of choice|0HTGB13FE2]], it has a [[choice function|0YXEQWRGP0]] $\sigma$. Put $s(C) = \sigma(S(C))$ and $g(C) = C \cup \{s(C)\}$.
5. Then $s(C)$ is a strict upper bound of $C$. So $s(C) \notin C$, and $g(C)$ is a chain.
6. Let $C$ be a chain. A segment of $C$ is a subset $T \subseteq C$ such that $x \in C$, $y \in T$ and $x \le y$ imply $x \in T$.
7. A segment of a segment of $C$ is a segment of $C$. A union of segments of $C$ is a segment of $C$. Both follow at once from the definition.
8. Call a chain $C$ good when, for each segment $T$ of $C$ with $T \neq C$, the chain $g(T)$ is a segment of $C$.
9. Comparison lemma: if $C_1$ and $C_2$ are good, one of them is a segment of the other. Let $M$ be the union of all sets that are segments of both $C_1$ and $C_2$.
10. By step 7, $M$ is a segment of both $C_1$ and $C_2$. Suppose $M \neq C_1$ and $M \neq C_2$.
11. Since $C_1$ and $C_2$ are good, $g(M)$ is a segment of both. So $g(M) \subseteq M$ by the definition of $M$. This contradicts $s(M) \notin M$ from step 5.
12. Hence $M = C_1$ or $M = C_2$, and $C_1$ is a segment of $C_2$ or $C_2$ is a segment of $C_1$. This proves the lemma.
13. Let $U$ be the union of all good chains. Let $x, y \in U$, with $x \in C$ and $y \in D$ for good chains $C, D$. By step 12, one of $C, D$ contains the other. So $x$ and $y$ lie in one chain and are comparable. Thus $U$ is a chain.
14. Each good chain $D$ is a segment of $U$. Let $x \in U$, $y \in D$ and $x \le y$. Pick a good chain $C$ with $x \in C$.
15. By step 12, $C \subseteq D$, so $x \in D$; or $D$ is a segment of $C$, and then $x \in D$ because $x \in C$, $y \in D$ and $x \le y$.
16. The chain $U$ is good. Let $T$ be a segment of $U$ with $T \neq U$. Pick $u \in U \setminus T$ and a good chain $D$ with $u \in D$.
17. Let $t \in T$. If $u \le t$, then $u \in T$, since $T$ is a segment of $U$; this is false. As $U$ is a chain, $t < u$. Since $D$ is a segment of $U$ (step 14), $t \in D$.
18. So $T \subseteq D$. Then $T$ is a segment of $D$, because it is a segment of the larger set $U$. Also $T \neq D$, because $u \in D \setminus T$.
19. As $D$ is good, $g(T)$ is a segment of $D$. As $D$ is a segment of $U$, step 7 shows that $g(T)$ is a segment of $U$. So $U$ is good.
20. Let $w = s(U)$ and $V = g(U) = U \cup \{w\}$. By step 5, $V$ is a chain and $w > x$ for all $x \in U$.
21. The set $U$ is a segment of $V$. Indeed, if $x \in V$, $y \in U$ and $x \le y$, then $x \neq w$, since $w \le y$ would give $w \le y < w$. So $x \in U$.
22. The chain $V$ is good. Let $T$ be a segment of $V$ with $T \neq V$. If $w \in T$, then each $x \in U$ has $x \le w$, so $x \in T$, and $T = V$, which is false. So $T \subseteq U$, and $T$ is a segment of $U$.
23. If $T = U$, then $g(T) = V$ is a segment of $V$. If $T \neq U$, then $g(T)$ is a segment of $U$ by step 19, hence of $V$ by steps 21 and 7.
24. So $V$ is a good chain, and $V \subseteq U$ by the definition of $U$. Then $w \in U$, which contradicts $w \notin U$ from step 5.
25. Hence the assumption in step 1 is false, and $P$ has a maximal element.

## Idea

If nothing is maximal, the axiom of choice lets us extend every chain by one strictly larger element. Good chains are the chains built step by step with these extensions, and any two of them agree as far as both go. Their union is then the largest good chain, yet it can still be extended once more, which is impossible.