Wosets are Isomorphic to Each Other or Initial Segments/Proof Without Using Choice

This article needs to be tidied. Please fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Tidy}} from the code.

This article needs proofreading. Please check it for mathematical errors. If you believe there are none, please remove {{Proofread}} from the code. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Proofread}} from the code.

Theorem

Let $\struct {S, \preceq_S}$ and $\struct {T, \preceq_T}$ be well-ordered sets.

Then precisely one of the following hold:

$\struct {S, \preceq_S}$ is order isomorphic to $\struct {T, \preceq_T}$

or:

$\struct {S, \preceq_S}$ is order isomorphic to an initial segment in $\struct {T, \preceq_T}$

or:

$\struct {T, \preceq_T}$ is order isomorphic to an initial segment in $\struct {S, \preceq_S}$

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 = \struct {S, \preceq_S} \cup \struct {T, \preceq_T}$

Define the following relation $\preceq$ on $U$:

$\forall x, y \in U: x \preceq y$

if and only if:

$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 = \O$

or:

$X \cap T = \O$

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: \struct {T, \preceq_T} \to \struct {U, \preceq}$:

$\map 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 $\II_x$ denote the initial segment in $U$ determined by $x$, according to $k$.

Note that $\II_x = \II_{\map k x}$, because $\map k x = x$.

Suppose $x \in S$.

Then $\II_x \subseteq S$ because $\preceq$ is a well-ordering.

Thus there is an order isomorphism from $T$ to $\II_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 $\II_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 $\II_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 Well-Ordered Class is not Isomorphic to Initial Segment.

$\blacksquare$

Sources

• 2000: James R. Munkres: Topology (2nd ed.): Supplementary Exercises $1.4$