# Kuratowski's Lemma

## Theorem

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.

## Proof

Let $S$ be a (non-empty) ordered set.

Let $C$ be a chain in $S$.

Let $P$ be the set of all chains that are supersets of $C$.

Let $\CC$ be a chain in $\powerset P$ (partially ordered by set-inclusion).

Define $C' = \bigcup \CC$.

Note that the elements of $P$ are chains on $\paren S$, so the elements of $\CC$ are also chains in $S$, as $\CC$ is a subset of $P$.

Thus $\bigcup \CC$ contains elements in $S$, so:

$C' \subseteq S$.

First, note that $C'$ is a chain in $S$.

Let $x, y \in C'$, which means $x \in X$ and $y \in Y$ for some $X, Y \in \CC$.

However, as $\CC$ is a chain in $\powerset P$, that means either $X \subseteq Y$ or $Y \subseteq X$.

So $x$ and $y$ belong to the same chain in $S$.

Thus either $x \le y$ or $y \le x$.

Thus $C'$ is a chain on $S$.

Now let $x \in C$.

Then:

$\forall A \in P: x \in A$

Then because $\CC \subseteq P$:

$\forall A \in \CC: x \in A$

So:

$x \in \bigcup \CC$

and so $C \subseteq C'$

Thus:

$C' \in P$

Now, note $C'$ is an upper bound on $\CC$.

To prove this consider $x \in D \in \CC$.

This means:

$x \in \bigcup \CC = C'$

so:

$D\subseteq C'$

The chain in $P$ was arbitrary, so every chain in $P$ has an upper bound.

Thus, by Zorn's Lemma, $P$ has a maximal element.

This must be a maximal chain containing $C$.

$\blacksquare$

## Note

One can also prove that Zorn's lemma follows from Kuratowski's Lemma, which shows that they are equivalent statements. Thus, this is another statement equivalent to the Axiom of Choice.

## Source of Name

This entry was named for Kazimierz Kuratowski.

## Historical Note

Kazimierz Kuratowski published what is now known as Kuratowski's Lemma in $1922$, thinking it little more than a corollary of the Hausdorff Maximal Principle.

In $1935$, Max August Zorn published his own equivalent, now known as Zorn's Lemma, acknowledging Kuratowski's earlier work.

This later version became the more famous one.