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