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

From ProofWiki
Jump to navigation Jump to search

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

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

Define:

$S' = S \cup \text{ initial segments in } S$
$T' = T \cup \text{ initial segments in } T$
$\mathcal F = \left\{ { f:S' \to T' \ \vert \ f \text{ is an order isomorphism} } \right\}$

We note that $\mathcal F$ is not empty, because it at least contains a trivial order isomorphism between singletons:

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

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 Ordered Product of Tosets is Totally Ordered Set, $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 $\mathcal F$.

Let $f_1$ be a maximal element of $\mathcal F$. 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 $f_1\left({a}\right) = 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 No Isomorphism from Woset to Initial Segment.

$\blacksquare$

Axiom of Choice

This theorem depends on the Axiom of Choice, by way of Zorn's Lemma.

Because of some of its bewilderingly paradoxical implications, the Axiom of Choice is considered in some mathematical circles to be controversial.

Most mathematicians are convinced of its truth and insist that it should nowadays be generally accepted.

However, others consider its implications so counter-intuitive and nonsensical that they adopt the philosophical position that it cannot be true.


Sources