Wosets are Isomorphic to Each Other or Initial Segments/Proof Without Using Choice
Theorem
Let $\left({S, \preceq_S}\right)$ and $\left({T, \preceq_T}\right)$ be well-ordered sets.
Then precisely one of the following hold:
- $\left({S, \preceq_S}\right)$ is order isomorphic to $\left({T, \preceq_T}\right)$
or:
- $\left({S, \preceq_S}\right)$ is order isomorphic to an initial segment in $\left({T, \preceq_T}\right)$
or:
- $\left({T, \preceq_T}\right)$ is order isomorphic to an initial segment in $\left({S, \preceq_S}\right)$
Proof
If the sets $S$ and $T$ considered are empty or singletons, the theorem holds vacuously or trivially.
Thus assume $S$ and $T$ each contain at least two elements.
Let $U = \left({S, \preceq_S}\right) \cup \left({T, \preceq_T}\right)$
Define the following relation $\preceq$ on $U$:
- $\forall x, y \in U: x \preceq y$
- $x, y \in S : x \preceq_S y$
or:
- $x, y \in T: x \preceq_T y$
or:
- $x \in S, y \in T$
We claim that $\preceq$ is a well-ordering.
First, we show it is a total ordering.
Checking in turn each of the criteria for a total ordering:
Reflexivity
If $x = y$, they're necessarily both in $S$ or $T$ simultaneously.
Reflexivity then follows from $\preceq_S$ and $x \preceq_T$ being reflexive, as they are both orderings.
Transitivity
Let $x, y, z \in U$.
If $x, y , z \in S$ or $x, y , z \in T$ simultaneously, then $\preceq$ is transitive by the transitivity of $\preceq_S$ and $\preceq_T$.
Suppose $x, y \in S$ and $z \in T$.
Let $x \preceq y$ and $y \preceq z$.
Then $x \preceq z$ because $x \in S$ and $y \in T$.
Suppose $x \in S$ and $y, z \in T$.
Then $x \preceq z$ also because $x \in S$ and $y \in T$.
Thus $\preceq$ is transitive.
Antisymmetry
Let $x \preceq y$ and $y \preceq x$.
If $x, y \in S$ then $x = y$ by the antisymmetry of $\preceq_S$.
Likewise if $x, y \in T$.
If $x \in S$ and $y \in T$, then $y \in S$ and $x \in T$ as well.
Thus $x = y$ from the antisymmetry of $\preceq_S$ or $\preceq T$.
Conclude that $\preceq$ is a total ordering.
To show $\preceq$ is a well-ordering, consider a non-empty set $X \subseteq U$.
Then either:
- $X \cap S = \varnothing$
or:
- $X \cap T = \varnothing$
or:
- $X \cap S$ is non-empty and $X \cap T$ is non-empty.
In the first case, $X \subseteq T$, by Intersection with Complement is Empty iff Subset.
Then $X$ has a smallest element defined by $\preceq_T$.
In the second case, $X \subseteq S$, also by Intersection with Complement is Empty iff Subset.
Then $X$ has a smallest element defined by $\preceq_S$.
In the third case, the smallest element of $X \setminus T$ is an element of $S$.
Thus it precedes any element of $T$ by the definition of $\preceq$.
The smallest element of $X \setminus T$, which is a subset of $S$, is guaranteed to exist by the well-ordering on $S$.
This smallest element is then also the smallest element of $\left({X \setminus T}\right) \cup T = X$.
Thus $\preceq$ is a well-ordering on $S \cup T$.
$\Box$
Consider the mapping:
- $k: \left({T, \preceq_T}\right) \to \left({U, \preceq}\right)$:
- $k(\alpha) = \alpha$
Then $k$ is strictly increasing, by the construction of $\preceq$.
Thus there is a strictly increasing mapping from $T$ to $U$.
From Strictly Increasing Mapping Between Wosets Implies Order Isomorphism, $T$ is order isomorphic to $U$ or an initial segment of $U$.
Let $\mathcal I_x$ denote the initial segment in $U$ determined by $x$, according to $k$.
Note that $\mathcal I_x = \mathcal I_{k(x)}$, because $k(x) = x$.
Suppose $x \in S$.
Then $\mathcal I_x \subseteq S$ because $\preceq$ is a well-ordering.
Thus there is an order isomorphism from $T$ to $\mathcal I_x$ in $S$.
Suppose $x = \min T$, the smallest element of $T$.
Then every element of $S$ strictly precedes $x$, as $x$ is in $T$.
Also, $x$ precedes every element of $T$, so $\mathcal I_x \ne T$.
Thus there is an order isomorphism from $T$ to all of $S$.
Suppose $x \in T$ and $x \ne \min T$.
Then $\mathcal I_x$ defines an initial segment in $T$.
Also, every element of $S$ strictly precedes $x$, as $x$ is in $T$.
Thus there is an order isomorphism from an initial segment of $T$ to all of $S$.
The cases are distinct by No Isomorphism from Woset to Initial Segment.
$\blacksquare$
Sources
- 2000: James R. Munkres: Topology (2nd ed.): Supplementary Exercises $1.4$