Order Sum of Totally Ordered Sets is Totally Ordered

Theorem

Let $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ be totally ordered sets.

Then the order sum $\struct {S_1, \preccurlyeq_1} \oplus \struct {S_2, \preccurlyeq_2}$ of $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ is also a totally ordered set.

Proof

Let $\struct {S, \preccurlyeq} := \struct {S_1, \preccurlyeq_1} \oplus \struct {S_2, \preccurlyeq_2}$.

From Order Sum of Ordered Sets is Ordered, $\struct {S, \preccurlyeq}$ is an ordered set.

It remains to be shown that $\tuple {a, b}$ and $\tuple {c, d}$ are comparable for all $\tuple {a, b}, \tuple {c, d} \in S$.

Let $\tuple {a, b}, \tuple {c, d} \in S$ be arbitrary.

By definition:

$\forall \tuple {a, b}, \tuple {c, d} \in S: \tuple {a, b} \preccurlyeq \tuple {c, d} \iff \begin {cases} b = 0 \text { and } d = 1 \\ b = d = 0 \text { and } a \preccurlyeq_1 c \\ b = d = 1 \text { and } a \preccurlyeq_2 c \end {cases}$

Let $a, c \in S_1$.

Then as $\preccurlyeq_1$ is a total ordering, $a$ and $c$ are comparable.

Hence by definition of $\oplus$ it follows that $\tuple {a, b}$ and $\tuple {c, d}$ are comparable.

Let $a, c \in S_2$.

Then as $\preccurlyeq_2$ is a total ordering, $a$ and $c$ are comparable.

Hence by definition of $\oplus$ it follows that $\tuple {a, b}$ and $\tuple {c, d}$ are comparable.

Finally, let $a \in S_1$ and $c \in S_2$.

Then $\tuple {a, 0} \in S$ and $\tuple {c, 1} \in S$.

Hence by definition of $\oplus$ it follows that $\tuple {a, b} \preccurlyeq \tuple {c, d}$ and so are comparable.

In all cases, $\tuple {a, b}$ and $\tuple {c, d}$ are comparable.

$\blacksquare$

Sources

• 1996: Winfried Just and Martin Weese: Discovering Modern Set Theory. I: The Basics ... (previous) ... (next): Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: Exercise $26 \ \text {(b)}$