Well Ordering

Overview

A non-strict well ordering on $A$ is a non-strict total order on $A$ with the additional property that every nonempty subset of $A$ has a minimum element.

A strict well ordering on $A$ is a strict total order on $A$ with the additional property that every nonempty subset of $A$ has a minimal element.

In the context of well orderings, an infinitely descending chain on set $A$ is an infinitely descending sequence into $A$ . That is, a function $f : ω \to A$ such that for all $n \in ω$ , $f (n^{+}) < f (n)$ . A strict total ordering is a well ordering if and only if there is no infinitely descending chain.

We say a set $A$ is well ordered by epsilon if and only if the following relation is a well ordering on $A$ :

\in_{A} = {⟨ x, y ⟩ \in A \times A ∣ x \in y}

Initial Segments

Let $<$ be a strict well ordering on set $A$ . Then the initial segment up to $t$ , for some $t \in A$ , is

{seg}_{<} t = {x \in A ∣ x < t} .

For a set $B$ , define set $^{< A} B$ and class $^{< A} V$ respectively as

\begin{aligned} ^{< A} B & = {f ∣ for some t \in A, f is a function from {seg}_{<} t into B}, \\ ^{< A} V & = {f ∣ for some t \in A, f is a function with dom f = {seg}_{<} t} . \end{aligned}

Trichotomy

For any two well-ordered structures, either they are isomorphic or one is isomorphic to an initial segment of the other. More precisely, let $<_{A}$ and $<_{B}$ be well orderings on $A$ and $B$ respectively. Then exactly one of the following holds:

$⟨ A, <_{A} ⟩ ≃ ⟨ B, <_{B} ⟩$ ,
$⟨ A, <_{A} ⟩ ≃ ⟨ seg b, <_{B}^{\circ} ⟩$ for some $b \in B$ ,
$⟨ seg a, <_{A}^{\circ} ⟩ ≃ ⟨ B, <_{B} ⟩$ for some $a \in A$ .

Note the $°$ symbol is used to denote an induced ordering.

Well-Ordering Theorem

For any set $A$ , there is a well-ordering on $A$ .

Numeration Theorem

Any set is equinumerous to some ordinal number.