Cartesian Product of Ordered Sets is Ordered Set

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({S_1, \preceq_1}\right)$, $\left({S_2, \preceq_2}\right)$ be ordered sets.

Let $\left({S_1 \times S_2, \preceq}\right)$ be the Cartesian product of $\left({S_1, \preceq_1}\right)$ and $\left({S_2, \preceq_2}\right)$.


Then $\left({S_1 \times S_2, \preceq}\right)$ is also an ordered set.

Proof

Reflexivity

Let $\left({s, t}\right) \in S_1 \times S_2$.

By definition of reflexivity:

$s \preceq_1 s$ and $t \preceq_2 t$

Thus by definition of Cartesian product:

$\left({s, t}\right) \preceq \left({s, t}\right)$

Transitivity

Let $\left({s_1, t_1}\right), \left({s_2, t_2}\right), \left({s_3, t_3}\right) \in S_1 \times S_2$ such that

$\left({s_1, t_1}\right) \preceq \left({s_2, t_2}\right) \preceq \left({s_3, t_3}\right)$

By definition of Cartesian product:

$s_1 \preceq_1 s_2 \preceq_1 s_3$ and $t_1 \preceq_2 t_2 \preceq_2 t_3$

By definition of transitivity:

$s_1 \preceq_1 s_3$ and $t_1 \preceq_2 t_3$

Thus by definition of Cartesian product:

$\left({s_1, t_1}\right) \preceq \left({s_3, t_3}\right)$

Antisymmetry

Let $\left({s_1, t_1}\right), \left({s_2, t_2}\right) \in S_1 \times S_2$ such that

$\left({s_1, t_1}\right) \preceq \left({s_2, t_2}\right)$ and $\left({s_2, t_2}\right) \preceq \left({s_1, t_1}\right)$

By definition of Cartesian product:

$s_1 \preceq_1 s_2$ and $s_2 \preceq_1 s_1$ and $t_1 \preceq_2 t_2$ and $t_2 \preceq_2 t_1$

By definition of antisymmetry:

$s_1 = s_2$ and $t_1 = t_2$

Thus:

$\left({s_1, t_1}\right) = \left({s_2, t_2}\right)$

$\blacksquare$


Sources