Unique Isomorphism between Equivalent Finite Totally Ordered Sets

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be finite sets of the same cardinality.

That is:

$\card S = \card T$

Let $\struct {S, \preceq}$ and $\struct {T, \preccurlyeq}$ be totally ordered sets.


Then there is exactly one order isomorphism from $\struct {S, \preceq}$ to $\struct {T, \preccurlyeq}$.


Proof

It is sufficient to consider the case where $\struct {T, \preccurlyeq}$ is $\struct {\N_n, \le}$ for some $n \in \N$.

Let $A$ be the set of all $n \in \N$ such that if:

$(1): \quad S$ is any set such that $\card S = n$, and
$(2): \quad \preceq$ is any total ordering on $S$

then there is exactly one isomorphism from $\struct {S, \preceq}$ to $\struct {\N_n, \le}$.


$\O \in A$ from Empty Mapping is Mapping and Equivalence of Mappings between Finite Sets of Same Cardinality.


Now let $n \in A$.

Let $\struct {S, \preceq}$ be a totally ordered set with $n + 1$ elements.

By Finite Non-Empty Subset of Totally Ordered Set has Smallest and Greatest Elements, $S$ has a greatest element $b$.

Then $\card {S \setminus \set b} = n$ by Cardinality Less One.

The total ordering on $S \setminus \set b$ is the one induced from that on $S$.

So as $n \in A$, there exists a unique order isomorphism $f: S \setminus \set b \to \struct {\N_n, \le}$.

Let us define the mapping $g: S \to \N_{n + 1}$ as follows:

$\forall x \in S: \map g x = \begin{cases} \map f x: & x \in S \setminus \set b \\ n: & x = b \end{cases}$

This is the desired order isomorphism from $\struct {S, \preceq}$ to $\struct {\N_{n + 1}, \le}$.

Now let $h: \struct {S, \preceq}$ to $\struct {\N_{n + 1}, \le}$ be an order isomorphism.

Then $\map h b = n$ (it has to be).

So the restriction of $h$ to $S \setminus \set b$ is an isomorphism from $S \setminus \set b$ to $\struct {\N_n, \le}$, and hence $h = f$ (as $n \in A$, any such order isomorphism is unique).

Thus:

$\forall x \in S \setminus \set b: \map h x = \map f x = \map g x$

and:

$\map h b = n = \map g b$

thus $h = g$.

Therefore $n + 1 \in A$.


The result follows from the Principle of Mathematical Induction.

$\blacksquare$


Sources