## You are here

Homeproof of Zermelo's well-ordering theorem

## Primary tabs

# proof of Zermelo’s well-ordering theorem

Let $X$ be any set and let $f$ be a choice function on $\mathcal{P}(X)\setminus\{\emptyset\}$. Then define a function $i$ by transfinite recursion on the class of ordinals as follows:

$i(\beta)=f(X-\bigcup_{{\gamma<\beta}}\{i(\gamma)\})\text{ unless }X-\bigcup_{{% \gamma<\beta}}\{i(\gamma)\}=\emptyset\text{ or }i(\gamma)\text{ is undefined % for some }\gamma<\beta$ |

(the function is undefined if either of the unless clauses holds).

Thus $i(0)$ is just $f(X)$ (the least element of $X$), and $i(1)=f(X-\{i(0)\})$ (the least element of $X$ other than $i(0)$).

Define by the axiom of replacement $\beta=i^{{-1}}[X]=\{\gamma\mid i(\gamma)=x\text{ for some }x\in X\}$. Since $\beta$ is a set of ordinals, it cannot contain all the ordinals (by the Burali-Forti paradox).

Since the ordinals are well ordered, there is a least ordinal $\alpha$ not in $\beta$, and therefore $i(\alpha)$ is undefined. It cannot be that the second unless clause holds (since $\alpha$ is the least such ordinal) so it must be that $X-\bigcup_{{\gamma<\alpha}}\{i(\gamma)\}=\emptyset$, and therefore for every $x\in X$ there is some $\gamma<\alpha$ such that $i(\gamma)=x$. Since we already know that $i$ is injective, it is a bijection between $\alpha$ and $X$, and therefore establishes a well-ordering of $X$ by $x<_{X}y\leftrightarrow i^{{-1}}(x)<i^{{-1}}(y)$.

The reverse is simple. If $C$ is a set of nonempty sets, select any well ordering of $\bigcup C$. Then a choice function is just $f(a)=$ the least member of $a$ under that well ordering.

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