Simple Order Product of Pair of Totally Ordered Sets is Total iff One Factor is Singleton
Theorem
Let $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ be ordered sets.
Let $\struct {S_1, \preccurlyeq_1} \otimes^s \struct {S_2, \preccurlyeq_2}$ denote the simple (order) product of $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$.
Then $\struct {S_1, \preccurlyeq_1} \otimes^s \struct {S_2, \preccurlyeq_2}$ is a totally ordered set if and only if:
- either $S_1$ or $S_2$ is a singleton
and:
- both $\preccurlyeq_1$ and $\preccurlyeq_2$ are total orderings.
Proof
Let $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ be ordered sets.
Let $\struct {T, \preccurlyeq_s} := \struct {S_1, \preccurlyeq_1} \otimes^s \struct {S_2, \preccurlyeq_2}$.
First we note that from Simple Order Product of Pair of Ordered Sets is Ordered Set, $\struct {T, \preccurlyeq_s}$ is an ordered set.
We also note that from Ordering on Singleton is Total Ordering, if either $S_1$ or $S_2$ is a singleton then $\struct {S_1, \preccurlyeq_1}$ or $\struct {S_2, \preccurlyeq_2}$ respectively is a totally ordered set.
Sufficient Condition
Let $\struct {T, \preccurlyeq_s}$ be a totally ordered set.
Aiming for a contradiction, suppose either of the following hold:
- $(1): \quad$ neither $S_1$ nor $S_2$ is a singleton
- $(2): \quad$ either $\preccurlyeq_1$ or $\preccurlyeq_2$ is not a total ordering.
Without loss of generality, let $\struct {S_1, \preccurlyeq_1}$ be an ordered set such that $\preccurlyeq_1$ is specifically not a total ordering.
Then there exists $x, y \in S_1$ such that neither $x \preccurlyeq_1 y$ nor $y \preccurlyeq_1 x$.
Let $t \in S_2$.
Then:
\(\ds x\) | \(\not \preccurlyeq_1\) | \(\ds y\) | ||||||||||||
\(\, \ds \land \, \) | \(\ds t\) | \(\preccurlyeq_2\) | \(\ds t\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {x, t}\) | \(\not \preccurlyeq_s\) | \(\ds \tuple {y, t}\) | Definition of Simple Order Product |
and:
\(\ds y\) | \(\not \preccurlyeq_1\) | \(\ds x\) | ||||||||||||
\(\, \ds \land \, \) | \(\ds t\) | \(\preccurlyeq_2\) | \(\ds t\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {y, t}\) | \(\not \preccurlyeq_s\) | \(\ds \tuple {x, t}\) | Definition of Simple Order Product |
So neither $\tuple {x, t} \preccurlyeq_s \tuple {y, t}$ nor $\tuple {y, t} \preccurlyeq_s \tuple {x, t}$.
That is, $\struct {T, \preccurlyeq_s}$ is not a totally ordered set.
This directly contradicts our assertion that $\struct {T, \preccurlyeq_s}$ is totally ordered.
Similarly if $\struct {S_2, \preccurlyeq_2}$ be an ordered set such that $\preccurlyeq_2$ is specifically not a total ordering.
So, in order for $\struct {T, \preccurlyeq_s}$ to be a totally ordered set, both $\preccurlyeq_1$ and $\preccurlyeq_2$ need to be total orderings.
Now suppose that both $\preccurlyeq_1$ and $\preccurlyeq_2$ are total orderings, but that neither $S_1$ nor $S_2$ is a singleton.
Then:
- $\exists s_1, t_1 \in S_1$ such that $s_1 \ne t_1$
- $\exists s_2, t_2 \in S_2$ such that $s_2 \ne t_2$.
Without loss of generality, let $s_1 \preccurlyeq_1 t_1$ and $s_2 \preccurlyeq_2 t_2$
Then we have:
\(\ds s_1\) | \(\preccurlyeq_1\) | \(\ds t_1\) | ||||||||||||
\(\, \ds \land \, \) | \(\ds s_2\) | \(\preccurlyeq_2\) | \(\ds t_2\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {s_1, s_2}\) | \(\preccurlyeq_s\) | \(\ds \tuple {t_1, t_2}\) | Definition of Simple Order Product |
But now consider $\tuple {s_1, t_2}, \tuple {s_2, t_1} \in T$.
\(\ds s_1\) | \(\preccurlyeq_1\) | \(\ds t_1\) | ||||||||||||
\(\, \ds \land \, \) | \(\ds t_2\) | \(\not \preccurlyeq_2\) | \(\ds s_2\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {s_1, t_2}\) | \(\not \preccurlyeq_s\) | \(\ds \tuple {s_2, t_1}\) | Definition of Simple Order Product | ||||||||||
\(\, \ds \land \, \) | \(\ds \tuple {s_2, t_1}\) | \(\not \preccurlyeq_s\) | \(\ds \tuple {s_1, t_2}\) |
That is, $\struct {T, \preccurlyeq_s}$ is not a totally ordered set.
This directly contradicts our assertion that $\struct {T, \preccurlyeq_s}$ is totally ordered.
Hence, by Proof by Contradiction, if $\struct {T, \preccurlyeq_s}$ is totally ordered then:
- either $S_1$ or $S_2$ is a singleton
and:
- both $\preccurlyeq_1$ and $\preccurlyeq_2$ are total orderings.
$\Box$
Necessary Condition
Let $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ be such that:
- either $S_1$ or $S_2$ is a singleton
and:
- both $\preccurlyeq_1$ and $\preccurlyeq_2$ are total orderings.
First let $S_1$ be a singleton.
From Ordering on Singleton is Total Ordering, $\struct {S_1, \preccurlyeq_1}$ is a totally ordered set.
Let $S_1 = \set s$.
Let $\tuple {s, x}$ and $\tuple {s, y}$ be arbitrary elements of $T$.
Then $x$ and $y$ are elements of $S_2$.
As $\struct {S_2, \preccurlyeq_2}$ is a totally ordered set, either $x \preccurlyeq_2 y$ or $y \preccurlyeq_2 x$.
Suppose $x \preccurlyeq_2 y$.
Then we have:
\(\ds s\) | \(\preccurlyeq_1\) | \(\ds s\) | as $\preccurlyeq_1$ is an ordering hence reflexive | |||||||||||
\(\, \ds \land \, \) | \(\ds x\) | \(\preccurlyeq_2\) | \(\ds y\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {s, x}\) | \(\preccurlyeq_s\) | \(\ds \tuple {s, y}\) | Definition of Simple Order Product |
Suppose $y \preccurlyeq_2 x$.
Then we have:
\(\ds s\) | \(\preccurlyeq_1\) | \(\ds s\) | as $\preccurlyeq_1$ is an ordering hence reflexive | |||||||||||
\(\, \ds \land \, \) | \(\ds y\) | \(\preccurlyeq_2\) | \(\ds x\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {s, y}\) | \(\preccurlyeq_s\) | \(\ds \tuple {s, x}\) | Definition of Simple Order Product |
Next let $S_2$ be a singleton.
From Ordering on Singleton is Total Ordering, $\struct {S_2, \preccurlyeq_2}$ is a totally ordered set.
Let $S_2 = \set t$.
Let $\tuple {x, t}$ and $\tuple {y, t}$ be arbitrary elements of $T$.
Then $x$ and $y$ are elements of $S_1$.
As $\struct {S_1, \preccurlyeq_1}$ is a totally ordered set, either $x \preccurlyeq_1 y$ or $y \preccurlyeq_1 x$.
Suppose $x \preccurlyeq_1 y$.
Then we have:
\(\ds x\) | \(\preccurlyeq_1\) | \(\ds y\) | ||||||||||||
\(\, \ds \land \, \) | \(\ds t\) | \(\preccurlyeq_2\) | \(\ds t\) | as $\preccurlyeq_2$ is an ordering hence reflexive | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {x, t}\) | \(\preccurlyeq_s\) | \(\ds \tuple {y, t}\) | Definition of Simple Order Product |
Suppose $y \preccurlyeq_1 x$.
Then we have:
\(\ds y\) | \(\preccurlyeq_1\) | \(\ds x\) | ||||||||||||
\(\, \ds \land \, \) | \(\ds t\) | \(\preccurlyeq_2\) | \(\ds t\) | as $\preccurlyeq_2$ is an ordering hence reflexive | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \tuple {y, t}\) | \(\preccurlyeq_s\) | \(\ds \tuple {x, t}\) | Definition of Simple Order Product |
As $\tuple {x, t}$ and $\tuple {y, t}$ are arbitrary, it follows that $\struct {T, \preccurlyeq_s}$ is a totally ordered set.
$\blacksquare$
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings: Exercise $14.18 \ \text {(c)}$