Woset is Isomorphic to Set of its Initial Segments

From ProofWiki
Jump to navigation Jump to search


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


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

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


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

where $\cong$ denotes order isomorphism.


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$.


$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.


$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$


$x \notin \map f x$


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

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


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.