Section 10: Well-Ordered Sets

A well-ordered set is a set with an order such that every its nonempty subset has a smallest element.

Constructing well-ordered sets, Well-Ordering Theorem

There are several ways of constructing well-ordered sets, for example:

A subset of a well-ordered set is well-ordered.
The product of a finite number of well-ordered sets can be well-ordered (in the dictionary order, for example).
The union of an arbitrary collection of disjoint well-ordered sets indexed by a well-ordered set can be well-ordered (compare first indexes, then elements).
Every nonempty finite ordered set has the order type of a section of $\mathbb{Z}_{+}$ , so is well-ordered.

Further, assuming the axiom of choice, every set can be well-ordered:

(Well-Ordering Theorem) For every set there is an order on it that is a well-ordering.

This theorem was proved by Zermelo in 1904, and it startled the mathematical world. There was considerable debate as to the correctness of the proof... When the proof was analyzed closely, the only point at which it was found that there might be some question was a construction involving an infinite number of arbitrary choices, that is, a construction involving — the choice axiom. Some mathematicians rejected the choice axiom as a result, and for many years a legitimate question about a new theorem was: Does its proof involve the choice axiom or not?.. Present-day mathematicians, by and large, do not have such qualms. They accept the axiom of choice as a reasonable assumption about set theory, and they accept the well-ordering theorem along with it.

In fact, neither accepting nor rejecting the axiom of choice leads to a contradiction. This is purely a matter of choice — which math universe is more suitable for the current purposes.

The axiom of choice is equivalent to the well-ordering theorem, see Supplementary Exercises.
A weaker result is of primary interest: there exists an uncountable well-ordered set.

Examples

Minimal uncountable well-ordered set

A section $S_{\alpha}$ of a well-ordered set is defined by $S_{\alpha}=\{x|x<\alpha\}$ .

Minimal uncountable well-ordered set: an uncountable well-ordered set $S_{\Omega}$ every section of which is countable. There exists such a set, and its order type is uniquely determined by the definition. $S_{\Omega}\cup\{\Omega\}$ is denoted by $\overline{S}_{\Omega}$ .

The proof of the existence of $S_{\Omega}$ uses the assumption that there exists an uncountable well-ordered set.

Every countable subset of $S_{\Omega}$ has an upper bound.
$S_{\Omega}$ has no largest element.
Every element of $S_{\Omega}$ has an immediate successor.
There are uncountably many elements in $S_{\Omega}$ having no immediate predecessor.

Antidictionary order

Let $A\subset(\mathbb{Z}_{+})^{\omega}$ be the set of all sequences that are eventually $1$ . Then, the antidictionary order, which prescribes to compare sequences “from right to left”, i.e. by the last element in which the sequences differ, is a well-ordering on $A$ .

Facts

Let $A$ be an ordered set.

If $A$ is well-ordered, then it has the least upper bound property.
If $A$ is well-ordered, then every $a\in A$ except for the largest (if exists) has an immediate successor.
$A$ is not well-ordered iff it has a countable subset having the same order type as $\mathbb{Z}_{-}$ .
- $A$ is well-ordered iff every countable subset of $A$ is well-ordered.

Principle of transfinite induction & general principle of recursive definition

The Principle of Transfinite Induction. Let $A$ be a well-ordered set. $B\subset A$ is called inductive if for every $\alpha\in A$ , $S_{\alpha}\subset B$ implies $\alpha\in B$ . If $B$ is inductive, then $B=A$ (compare to the strong induction principle, Section 4).

The General Principle of Recursive Definition. (see Supplementary Exercises) Let $A$ be a well-ordered set and $B$ be a set. Further, let $F$ be the set of all functions from all sections of $A$ to $B$ , and $\rho:F\rightarrow B$ be a recursive rule. Then, there exists a unique function $h$ such that for $\alpha\in A$ : $h(\alpha)=\rho(h|S_{\alpha})$ (compare to the principle of recursive definition, Section 8).

Cardinality

For every two sets $A$ and $B$ either they have the same cardinality, or one has the cardinality greater than the other (assuming the well-ordering theorem).

Indeed, either there is a surjection from $A$ onto $B$ , implying there is an injection from $B$ into $A$ , or there is no surjection, and we can well-order the sets, and by the general principle of recursive definition define an injective function $h$ from $A$ to $B$ using $\rho(f:S_{\alpha}\rightarrow B)=smallest[B-f(S_{\alpha})]$ , in which case $h(\alpha)=smallest[B-h(S_{\alpha})]$ .

Subpages

Section 10: Well-Ordered Sets

Section 10: Well-Ordered Sets

Constructing well-ordered sets, Well-Ordering Theorem

Examples

Minimal uncountable well-ordered set

Antidictionary order

Facts

Principle of transfinite induction & general principle of recursive definition

Cardinality