Zorn's Lemma implies Kuratowski's Lemma
Theorem
Let Zorn's Lemma be accepted as true.
Then Kuratowski's Lemma holds.
Proof
Recall Zorn's Lemma:
Let $\struct {S, \preceq}, S \ne \O$ be a non-empty ordered set such that every non-empty chain in $S$ has an upper bound in $S$.
Then $S$ has at least one maximal element.
$\Box$
Recall Kuratowski's Lemma:
Let $\struct {S, \preceq}, S \ne \O$ be a non-empty ordered set.
Then every chain in $S$ is the subset of some maximal chain.
$\Box$
Let $\struct {S, \preceq}$ be a non-empty ordered set.
Let $C$ be a chain in $\struct {S, \preceq}$.
Let $T$ be the set of all chains in $\struct {S, \preceq}$ that are supersets of $C$.
Let $\CC$ be a chain in the power set $\powerset T$ of $T$ under the ordering that is the subset relation.
Define $C' = \bigcup \CC$ be the union of $\CC$.
We have that the elements of $T$ are chains on $\struct {S, \preceq}$.
We have that $\CC$ is a subset of $T$.
Hence the elements of $\CC$ are also chains in $\struct {S, \preceq}$.
Thus $\bigcup \CC$ contains elements in $\struct {S, \preceq}$.
Hence:
- $C' \subseteq S$
We have that $C'$ is a chain in $\struct {S, \preceq}$.
Let $x, y \in C'$.
Then $x \in X$ and $y \in Y$ for some $X, Y \in \CC$.
As $\CC$ is a chain in $\powerset T$:
- either $X \subseteq Y$ or $Y \subseteq X$.
So $x$ and $y$ belong to the same chain in $\struct {S, \preceq}$.
Thus either $x \preceq y$ or $y \preceq x$.
Thus $C'$ is a chain on $\struct {S, \preceq}$.
Now let $x \in C$.
Then:
- $\forall A \in T: x \in A$
Then because $\CC \subseteq T$:
- $\forall A \in \CC: x \in A$
So:
- $x \in \bigcup \CC$
and so:;
- $C \subseteq C'$
Thus:
- $C' \in T$
We now show that $C'$ is an upper bound on $\CC$.
Indeed, consider $x \in D \in \CC$.
This means:
- $x \in \bigcup \CC = C'$
so:
- $D\subseteq C'$
Thus $C'$ is an upper bound on $\CC$.
The chain in $T$ was arbitrary.
Hence every chain in $T$ has an upper bound.
Thus, by Zorn's Lemma, $T$ has a maximal element.
This must be a maximal chain containing $C$.
$\blacksquare$
Sources
- This article incorporates material from Equivalence of Kuratowski’s lemma and Zorn’s lemma on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.