Woset is Isomorphic to Set of its Initial Segments

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \preceq}$ be a well-ordered set.

Let:

$A = \set {a^\prec: a \in S}$

where $a^\prec$ is the strict lower closure of $S$ determined by $a$.


Then:

$\struct {S, \preceq} \cong \struct {A, \subseteq}$

where $\cong$ denotes order isomorphism.


Proof

Define $f: S \to A$ as:

$\forall a \in S: \map f a = a^\prec$

where $a^\prec$ is the initial segment determined by $a$.


$f$ is Surjective

$f$ is trivially surjective by the definition of $A$.

$\Box$


$f$ is Strictly Increasing

Let $x, y \in S$ with $x \prec y$.

Let $z \in \map f x$.

Then by the definition of initial segment:

$z \prec x$

By Reflexive Reduction of Ordering is Strict Ordering, $\prec$ is also transitive.

Thus:

$z \prec y$

Thus by the definition of initial segment:

$z \in y^\prec = \map f y$

As this holds for all such $z$:

$\map f x \subseteq \map f y$

As $x \prec y$:

$x \in y^\prec = \map f y$

But since $\prec$ is antireflexive:

$x \nprec x$

so:

$x \notin \map f x$

Thus:

$\map f x \subsetneqq \map f y$

As this holds for all such $x$ and $y$, $f$ is strictly increasing.

$\Box$


Since a well-ordering is a total ordering, $f$ is an order embedding by Mapping from Totally Ordered Set is Order Embedding iff Strictly Increasing.

Thus $f$ is a surjective order embedding and therefore an order isomorphism.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Woset_is_Isomorphic_to_Set_of_its_Initial_Segments&oldid=584052"