Simple Order Product of Pair of Totally Ordered Sets is Total iff One Factor is Singleton

From ProofWiki
Jump to navigation Jump to search

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