equivalence of Hausdorff’s maximum principle, Zorn’s lemma and the well-ordering theorem

Hausdorff’s maximum principle implies Zorn’s lemma.

Consider a partially ordered set $X$ , where every chain has an upper bound. According to the maximum principle there exists a maximal totally ordered subset $Y\subseteq X$ . This then has an upper bound, $x$ . If $x$ is not the largest element in $Y$ then $\{x\}\cup Y$ would be a totally ordered set in which $Y$ would be properly contained, contradicting the definition. Thus $x$ is a maximal element in $X$ .

Zorn’s lemma implies the well-ordering theorem.

Let $X$ be any non-empty set, and let $\mathcal{A}$ be the collection of pairs $(A,\leq)$ , where $A\subseteq X$ and $\leq$ is a well-ordering on $A$ . Define a relation $\preceq$ , on $\mathcal{A}$ so that for all $x,y\in\mathcal{A}:x\preceq y$ iff $x$ equals an initial of $y$ . It is easy to see that this defines a partial order relation on $\mathcal{A}$ (it inherits reflexibility, anti symmetry and transitivity from one set being an initial and thus a subset of the other).

For each chain $C\subseteq\mathcal{A}$ , define $C^{\prime}=(R,\leq^{\prime})$ where R is the union of all the sets $A$ for all $(A,\leq)\in C$ , and $\leq^{\prime}$ is the union of all the relations $\leq$ for all $(A,\leq)\in C$ . It follows that $C^{\prime}$ is an upper bound for $C$ in $\mathcal{A}$ .

According to Zorn’s lemma, $\mathcal{A}$ now has a maximal element, $(M,\leq_{M})$ . We postulate that $M$ contains all members of $X$ , for if this were not true we could for any $a\in X-M$ construct $(M_{*},\leq_{*})$ where $M_{*}=M\cup\{a\}$ and $\leq_{*}$ is extended so $S_{a}(M_{*})=M$ . Clearly $\leq_{*}$ then defines a well-order on $M_{*}$ , and $(M_{*},\leq_{*})$ would be larger than $(M,\leq_{M})$ contrary to the definition.

Since $M$ contains all the members of $X$ and $\leq_{M}$ is a well-ordering of $M$ , it is also a well-ordering on $X$ as required.

The well-ordering theorem implies Hausdorff’s maximum principle.

Let $(X,\preceq)$ be a partially ordered set, and let $\leq$ be a well-ordering on $X$ . We define the function $\phi$ by transfinite recursion over $(X,\leq)$ so that

\phi(a)=\begin{cases}\{a\}&\text{if }\{a\}\cup\bigcup_{b<a}\phi(b)\text{ is % totally ordered under }\preceq.\\ \emptyset&\text{otherwise}.\end{cases}.

It follows that $\bigcup_{x\in X}\phi(x)$ is a maximal totally ordered subset of $X$ as required.

Title	equivalence of Hausdorff’s maximum principle, Zorn’s lemma and the well-ordering theorem
Canonical name	EquivalenceOfHausdorffsMaximumPrincipleZornsLemmaAndTheWellorderingTheorem
Date of creation	2013-03-22 13:04:45
Last modified on	2013-03-22 13:04:45
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	9
Author	mathcam (2727)
Entry type	Proof
Classification	msc 03E25
Synonym	proof ofZorn’s lemma
Synonym	proof of Hausdorff’s maximum principle
Synonym	proof of the maximum principle
Related topic	ZornsLemma
Related topic	AxiomOfChoice
Related topic	ZermelosWellOrderingTheorem
Related topic	HaudorffsMaximumPrinciple