## You are here

Homeequivalence of Hausdorff's maximum principle, Zorn's lemma and the well-ordering theorem

## Primary tabs

# 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.

## Mathematics Subject Classification

03E25*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

new problem: Problem: Show that phi(a^n-1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia

new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz

Mar 26

new correction: Misspelled name by DavidSteinsaltz

Mar 21

new correction: underline-typo by Filipe

Mar 19

new correction: cocycle pro cocyle by pahio

Mar 7

new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier

new image: expected waiting time by robert_dodier

new image: plot W(t) = P(waiting time <= t) by robert_dodier