Equality to Initial Segment Imposes Well-Ordering
Theorem
Let $X$ be a set.
Let $\AA$ be the set of all ordered pairs $\struct {A, <}$ such that $A$ is a subset of $X$ and $<$ is a strict well-ordering of $A$.
Define $\prec$ as:
- $\struct {A, <} \prec \struct {A', <'}$
- $\struct {A, <}$ equals an initial segment of $\struct {A', <'}$.
Let $\BB$ be a set of ordered pairs in $\AA$ such that $\BB$ is ordered by $\prec$.
Let $B'$ be the union of the sets $B$ for all $\struct {B, <} \in \BB$.
Let $<'$ be the union of the relations $<$ for all $\struct {B, <}$.
Then $\struct {B', <'}$ is strictly well-ordered set.
Proof
If the set $X$ considered is empty or a singleton, the lemma holds vacuously or trivially.
Thus assume $X$ contains at least two elements.
We first prove that $\prec$ is a strict partial ordering on $\AA$.
From the definition of initial segment, no $\struct {A, <}$ can equal an initial segment of itself.
Thus $\prec$ is antireflexive.
Suppose $\struct {A, <_A}$ equals an initial segment of $\struct {B, <_B}$ and $\struct {B, <_B}$ equals an initial segment of $\struct {C, <_C}$.
Then $\struct {A, <_A}$ equals an initial segment of $\struct {C, <'}$ from Equality is Transitive.
Thus $\prec$ is a strict partial ordering on $\AA$.
We then prove that any $\struct {B', <'}$ is a strictly well-ordered set.
Let $x_1,x_2 \in B'$.
That is, let $x_i \in \struct {A_i, <_i}$ for $i = 1, 2$.
Suppose $x_2 \prec x_1$.
That is, $\struct {A_2, <_2}$ equals an initial segment in $\struct {A_1, <_1}$
By the definition of initial segment, both $x_1$ and $x_2$ are in $\struct {A_1, <_1}$.
Thus $<'$ is connected, as all $<_i$ are strict well-orderings by hypothesis.
For any $x_i \in \struct {A_i, <_i}$, $x_i \nprec x_i$ as all $<_i$ are strict well-orderings by hypothesis.
Thus $<'$ is antireflexive.
To show that $<'$ is transitive, consider $x_i \in \struct {B', <'}$ for $i = 1, 2, 3$.
Suppose $x_1 <' x_2 <' x_3$.
Then $x_1 <_1 x_2$ and $x_2 <_2 x_3$, from the definition of $<'$ as a union of relations $<_i$.
Then $\struct {A_j, <_j}$ is an initial segment of $\struct {A_i, <_i}$ for $j = 1, 2; j < i$
Thus $x_1 <_i x_2 <_i x_3$.
Then $x_1 <_i x_3$, as all $<_i$ as all $<_i$ are strict well-orderings by hypothesis.
Conclude that $<'$ is itself a strict ordering.
It remains to be shown that $<'$ is a well-ordering.
Let $A$ be an arbitrary non-empty subset of $B'$.
Let $x \in A$ and $x \in \struct {B, <}$ for $\struct {B, <} \in \BB$.
Then for all $y \in A$, $y <' x$ if and only if $y < x$ and $y \in B$.
As $<$ is a well-ordering, $\struct {B \cap A, <}$ has a smallest element $b$.
This $b$ is then a smallest element of $<'$ in $A$.
Conclude that $<'$ is a strict well-ordering on $B'$.
$\blacksquare$
Sources
- 2000: James R. Munkres: Topology (2nd ed.): Supplementary Exercises $1.5$