Simple Order Product of Pair of Ordered Sets is Ordered Set

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 also an ordered set.


Proof

Let $\struct {T, \preccurlyeq_s} := \struct {S_1, \preccurlyeq_1} \otimes^s \struct {S_2, \preccurlyeq_2}$.


By definition of simple product:

$T := S_1 \times S_2$ where $\times$ denotes Cartesian product
$\forall \tuple {a, b}, \tuple {c, d} \in T: \tuple {a, b} \preccurlyeq_s \tuple {c, d} \iff a \preccurlyeq_1 c \text { and } b \preccurlyeq_2 d$

We check in turn each of the criteria for an ordering:


Reflexivity

We have by definition of Cartesian product:

$\forall \tuple {a, b} \in S_1 \times S_2: a \in S_1 \land b \in S_2$

As $\preccurlyeq_1$ and $\preccurlyeq_2$ are both orderings, they are themselves both reflexive.

Hence both $a \preccurlyeq_1 a$ and $b \preccurlyeq_2 b$.

Hence by definition of simple product:

$\forall \tuple {a, b} \in S: \tuple {a, b} \preccurlyeq_s \tuple {a, b}$


So $\preccurlyeq_s$ is reflexive.

$\Box$


Transitivity

Suppose $\tuple {a, b} \preccurlyeq_s \tuple {c, d}$ and $\tuple {c, d} \preccurlyeq_s \tuple {e, f}$.

Then by definition of simple product:

$a \preccurlyeq_1 c$ and $b \preccurlyeq_2 d$
$c \preccurlyeq_1 e$ and $d \preccurlyeq_2 f$

As $\preccurlyeq_1$ and $\preccurlyeq_2$ are both orderings, they are themselves both transitive.

Hence:

$a \preccurlyeq_1 e$ and $b \preccurlyeq_2 f$

By definition of simple product:

$\tuple {a, b} \preccurlyeq_s \tuple {e, f}$

So $\preccurlyeq_s$ is transitive.

$\Box$


Antisymmetry

Suppose $\tuple {a, b} \preccurlyeq_s \tuple {c, d}$ and $\tuple {c, d} \preccurlyeq_s \tuple {a, b}$.

Then by definition of simple product:

$a \preccurlyeq_1 c$ and $b \preccurlyeq_2 d$
$c \preccurlyeq_1 a$ and $d \preccurlyeq_2 b$

As $\preccurlyeq_1$ and $\preccurlyeq_2$ are both orderings, they are themselves both antisymmetric.

Hence:

$a = c$ and $b = d$

So by Equality of Ordered Pairs:

$\tuple {a, c} = \tuple {b, d}$

So $\preccurlyeq_s$ is antisymmetric.

$\Box$


So we have shown that $\preccurlyeq_s$ is reflexive, transitive and antisymmetric.

Thus by definition, $\preccurlyeq_s$ is an ordering and so $\struct {S_1, \preccurlyeq_1} \otimes^s \struct {S_2, \preccurlyeq_2}$ is an ordered set.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Simple_Order_Product_of_Pair_of_Ordered_Sets_is_Ordered_Set&oldid=567269"