Well-Ordering Theorem
Contents |
Theorem
Every set is well-orderable.
Proof
Let $S$ be a set, and let $\mathcal P \left({S}\right)$ be the power set of $S$.
By the Axiom of Choice, there is a choice function $c$ defined on $\mathcal P \left({S}\right) - \left\{{\varnothing}\right\}$.
We will use this choice function and the Principle of Transfinite Induction to define a bijection between $S$ and some ordinal.
Intuitively, we start by pairing $c \left({S}\right)$ with $0$, and then keep extending the bijection by pairing $c \left({S - X}\right)$ with $\alpha$, where $X$ is the set of elements we've dealt with already.
- Base case
- $\alpha = 0$
Let $s_0 = c \left({S}\right)$.
- Inductive step
- Suppose $s_\beta$ has been defined for all $\beta < \alpha$.
If $S - \left\{{s_\beta: \beta < \alpha}\right\}$ is empty, we stop.
Otherwise, define:
- $s_\alpha := c \left({S - \left\{{s_\beta: \beta < \alpha}\right\} }\right)$.
The process eventually stops, else we have defined bijections between subsets of $S$ and arbitrarily large ordinals.
You can help ProofWiki by adding precise reasons why such statements hold.
To discuss it in more detail, feel free to use the talk page.
If you are able to do this, then when you have done so you can 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 (see the proofread template for usage).
Now, we can impose a well-ordering on $S$ by embedding it via $s_\alpha \to \alpha$ into the ordinal $\beta = \displaystyle{\bigcup_{s_\alpha \in S} \alpha}$ and using the well-ordering of $\beta$.
$\blacksquare$
Alternative names
This result is also known as Zermelo's Theorem, for Ernst Zermelo.
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.
Axiom of Choice
This theorem depends on the Axiom of Choice.
Because of some of its bewilderingly paradoxical implications, the Axiom of Choice is considered in some mathematical circles to be controversial.
Most mathematicians are convinced of its truth and insist that it should nowadays be generally accepted.
However, others consider its implications so counter-intuitive and nonsensical that they adopt the philosophical position that it cannot be true.
In fact, the Well-Ordering Theorem is equivalent to the Axiom of Choice.
Sources
- Steven A. Gaal: Point Set Topology (1964)... (previous)... (next): Introduction to Set Theory: $3$. The Axiom of Choice and Its Equivalents
- T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 8$: Theorem $8.3$
