Wosets are Isomorphic to Each Other or Initial Segments

It has been suggested that this page be renamed. In particular: Fundamental Theorem of Well-Ordering To discuss this page in more detail, feel free to use the talk page.

This page has been identified as a candidate for refactoring of advanced complexity. In particular: Repurpose this so it uses well-ordered classes Until this has been finished, please leave {{Refactor}} in the code. New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$. 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 {{Refactor}} 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 Using Choice

We assume $S \ne \O \ne T$; otherwise the theorem holds vacuously.

Define:

$S' = S \cup \text{ initial segments in } S$

$T' = T \cup \text{ initial segments in } T$

$\FF = \set {f: S' \to T' \mid f \text{ is an order isomorphism} }$

We note that $\FF$ is non-empty, because it at least contains a trivial order isomorphism between singletons:

$f_0: \set {\text{smallest element in } S} \to \set {\text{smallest element in } T}$

Such smallest elements are guaranteed to exist by virtue of $S$ and $T$ being well-ordered.

By the definition of initial segment, the initial segments of $S$ are subsets of $S$.

For any initial segment $I_\alpha$ of $S$, such a segment has an upper bound by definition, namely, $\alpha$.

Also, no initial segment of $S'$ is the entirety of $S$.

Thus every initial segment of $S'$ has an upper bound, $S$ itself.

Every chain in $S'$ has an upper bound, because it defines an initial segment.

The previous reasoning also applies to $T'$.

By Antilexicographic Product of Totally Ordered Sets is Totally Ordered, $S' \times T'$ is itself a totally ordered set, with upper bound $S \times T$.

Thus the hypotheses of Zorn's Lemma are satisfied for $\FF$.

Let $f_1$ be a maximal element of $\FF$.

Call its domain $A$ and its codomain $B$.

Suppose $A$ is an initial segment $I_a$ in $S$ and $B$ is an initial segment $I_b$ in $T$.

Then $f_1$ can be extended by defining $\map {f_1} a = b$.

This would contradict $f_1$ being maximal, so it cannot be the case that both $A$ and $B$ are initial segments.

Then precisely one of the following hold:

$A = S$, with $S$ order isomorphic to an initial segment in $T$

or:

$B = T$, with $T$ order isomorphic to an initial segment in $S$

or:

both $A = S$ and $B = T$, with $S$ order isomorphic to $T$.

The cases are distinct by Well-Ordered Class is not Isomorphic to Initial Segment.

$\blacksquare$

Proof Without Using Choice

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$

Also see

• Counting Theorem