Tukey's Lemma/Formulation 1

Theorem

Let $S$ be a non-empty set of finite character.

Then $S$ has an element which is maximal with respect to the subset relation.

Proof

Let $C \subseteq S$ be a chain.

We will show that $\ds \bigcup C \in S$.

Let $x$ be a finite subset of $\ds \bigcup C$.

By the definitions of subset and of union, each element of $x$ is an element of at least one element of $C$.

By the Principle of Finite Choice, there is a mapping $c: x \to C$ such that:

$\forall a \in x: a \in \map c x$

Then $\map c x$ is a finite subset of $C$.

From Finite Totally Ordered Set is Well-Ordered, $\map c x$ has a greatest element $m \in C \subseteq S$.

Then:

$x$ is a finite subset of $m$

and:

$m \in S$

Since $S$ has finite character:

$x \in S$

We have thus shown that every finite subset of $\ds \bigcup C$ is in $S$.

Since $S$ is of finite character:

$\ds \bigcup C \in S$

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

$\blacksquare$

Axiom of Choice

This proof depends on the Axiom of Choice.

Because of some of its bewilderingly paradoxical implications, the Axiom of Choice is considered in some mathematical circles to be controversial.

Most mathematicians are convinced of its truth and insist that it should nowadays be generally accepted.

However, others consider its implications so counter-intuitive and nonsensical that they adopt the philosophical position that it cannot be true.

Also known as

Tukey's Lemma is still occasionally found with the name of Teichmüller attached to it, but this is dying out.

Source of Name

This entry was named for John Wilder Tukey.