Kuratowski's Lemma

From ProofWiki
Jump to navigation Jump to search

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.

Also see


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.


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.