Zermelo's Well-Ordering Theorem

From ProofWiki
(Redirected from Well-Ordering Theorem)
Jump to navigation Jump to search

Theorem

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.

$\blacksquare$


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.


This article contains statements that are justified by handwavery.
In particular: I think this can be fixed with Hartogs' Lemma (Set Theory)
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding precise reasons why such statements hold.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Handwaving}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.



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

$\blacksquare$


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$
and:
$F \restriction \beta$ is injective
and so $\beta$ can be put into a one-to-one correspondence with $S$.


This needs considerable tedious hard slog to complete it.
In particular: Proof needed for both $1$ and $2$ above
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Finish}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.


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.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Zermelo%27s_Well-Ordering_Theorem&oldid=656370"