# Cardinality, Zorn's Lemma

## Zorn's Lemma

Let S be a partially ordered set,
and assume every chain of elements,
i.e. linearly ordered subset of S,
has an upper bound.
Zorn's lemma
(biography)
says there is a maximal element m,
such that nothing is larger than m.
This does not mean m is maximum, greater than the rest of S,
only that m is maximal, with nothing larger.
Zorn's lemma is equivalent to the axiom of choice.
Either implies the other.

First assume the axiom of choice,
and let S be a partially ordered set whose chains are bounded.
Build an order preserving map from any ordinal a into S.
If there is no maximal element then there is
at least one larger element to map the successor ordinal to,
and we are given that every chain has an upper bound to map the limit ordinal to,
so the conditions of the recursion theorem with choice apply.
All the ordinals map 1-1 into S,
yet this is impossible,
hence there is a maximal element in S.
In fact every element of S lies beneath a maximal element.

Conversely, apply zorn's lemma to the well ordered subsets of S.
One well ordered subset (sequence) is less than another
if the latter is an extension of the former.
A maximal sequence must order all of S, or we could append one more element and find
a larger well ordered subset.
Thus zorn's lemma implies the well ordering principle,
and both are equivalent to choice.