Lexicographic Order of Family of Totally Ordered Sets is Totally Ordered Set

From ProofWiki
Jump to navigation Jump to search

Theorem

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

For each $i \in I$, let $\struct {S_i, \preccurlyeq_i}$ be a totally ordered set.

Let $\ds D = \prod_{i \mathop \in I} S_i$ be the Cartesian product of the family $\family {\struct {S_i, \preccurlyeq_i} }_{i \mathop \in I}$ indexed by $I$.

Let $\preccurlyeq_D$ be the lexicographic order on $D$, defined as:

$\forall u, v \in D: u \preccurlyeq_D v \iff \begin {cases} u = v \\ \map u i \preccurlyeq_i \map v i & \text {for the $\preceq$-smallest $i \in I$ such that $\map u i \ne \map v i$} \end {cases}$


Then $\struct {D, \preccurlyeq_D}$ is a totally ordered set.


Proof

From Lexicographic Product of Family of Ordered Sets is Ordered Set, $\struct {D, \preccurlyeq_D}$ is an ordered set.

It remains to be shown that $\struct {D, \preccurlyeq_D}$ is totally ordered.



Sources