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

From ProofWiki
Jump to navigation Jump to search


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.



This article needs to be linked to other articles.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links.
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 {{MissingLinks}} 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

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$


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

Retrieved from "https://proofwiki.org/w/index.php?title=Wosets_are_Isomorphic_to_Each_Other_or_Initial_Segments/Proof_Using_Choice&oldid=584055"