Zermelo's Well-Ordering Theorem

From ProofWiki
Jump to navigation Jump to search


Let the Axiom of Choice be accepted.

Then every set is well-orderable.

Proof 1

Let $S$ be a set.

Let $\powerset S$ be the power set of $S$.

By the Axiom of Choice, there exists a choice function on $S$.

The result follows from Set with Choice Function is Well-Orderable.


Proof 2

Let $S$ be a set.

Let $\powerset S$ be the power set of $S$.

By the Axiom of Choice, there is a choice function $c$ defined on $\powerset S \setminus \set \O$.

We will use $c$ and the Principle of Transfinite Induction to define a bijection between $S$ and some ordinal.

Intuitively, we start by pairing $\map c S$ with $0$, and then keep extending the bijection by pairing $\map c {S \setminus X}$ with $\alpha$, where $X$ is the set of elements already dealt with.

Basis for the Induction

$\alpha = 0$

Let $s_0 = \map c S$.

Inductive Step

Suppose $s_\beta$ has been defined for all $\beta < \alpha$.

If $S \setminus \set {s_\beta: \beta < \alpha}$ is empty, we stop.

Otherwise, define:

$s_\alpha := \map c {S \setminus \set {s_\beta: \beta < \alpha} }$

The process eventually stops, else we have defined bijections between subsets of $S$ and arbitrarily large ordinals.

Now, we can impose a well-ordering on $S$ by embedding it via $s_\alpha \to \alpha$ into the ordinal $\beta = \ds {\bigcup_{s_\alpha \mathop \in S} \alpha}$ and using the well-ordering of $\beta$.


Proof 3

Let $S$ be a non-empty set.

Let $C$ be a choice function for $S$.

Let $A$ be an arbitrary set.

Let the mapping $h$ be defined as:

$\map h A = \begin {cases}

\map C {S \setminus A} & : A \subsetneqq S \\ x & : \text {otherwise} \end {cases}$

where $x$ is an arbitrary element such that $x \notin S$.

The latter is known to exist from Exists Element Not in Set.

From the Transfinite Recursion Theorem: Formulation $5$, there exists a mapping $F$ on the class of all ordinals $\On$ such that:

$\forall \alpha \in \On: \map F \alpha = \map h {F \sqbrk \alpha}$

It remains to show the following:

$(1): \quad \exists \delta \in \On: \map F \delta \notin S$
$(2): \quad$ Let $\beta$ be the smallest ordinal such that $\map F \beta \notin S$. Then:
$F \sqbrk \beta = S$
$F \restriction \beta$ is injective
and so $\beta$ can be put into a one-to-one correspondence with $S$.

Hence $S$ can be well-ordered.

Also known as

Zermelo's Well-Ordering Theorem is also known just as the well-ordering theorem.

Some sources omit the hyphen: (Zermelo's) well ordering theorem.

It is also known just as Zermelo's Theorem.

Under this name it can often be seen worded:

Every set of cardinals is well-ordered with respect to $\le$.

This is called by some authors the Trichotomy Problem.

It is also referred to as the well-ordering principle, but this causes confusion with the result that states that the natural numbers are well-ordered.

Also see

Source of Name

This entry was named for Ernst Friedrich Ferdinand Zermelo.