Ordered Product of Tosets is Totally Ordered Set

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $S_1 \cdot S_2 = \left({S_1 \times S_2, \preceq}\right)$ be the ordered product of $S_1$ and $S_2$.


Then $\left({S_1 \times S_2, \preceq}\right)$ is itself a toset.


General Result

Let $S_1, S_2, \ldots, S_n$ all be tosets.

Let $T_n$ be the ordered product of $S_1, S_2, \ldots, S_n$:

$\forall n \in \N_{>0}: T_n = \begin{cases} S_1 & : n = 1 \\ T_{n-1} \cdot S_n & : n > 1 \end{cases}$

Then $T_n$ is a toset.


Proof

By definition of ordered product, we have that:

$b_1 \prec_2 b_2 \implies \left({a_1, b_1}\right) \prec \left({a_2, b_2}\right)$
$b_1 = b_2, a_1 \prec_1 a_2 \implies \left({a_1, b_1}\right) \prec \left({a_2, b_2}\right)$
$b_1 = b_2, a_1 = a_2 \implies \left({a_1, b_1}\right) = \left({a_2, b_2}\right)$


We note that as $\left({S_1, \preceq_1}\right)$ and $\left({S_2, \preceq_2}\right)$ are both tosets, then $\preceq_1$ and $\preceq_2$ are both connected.

Thus it is clear that $\preceq$ is connected.


Now we check in turn each of the criteria for an ordering:


Reflexivity

We have by definition of set union:

$\forall \left({a, b}\right) \in S_1 \times S_2: a = a \land b = b$

and so $\left({a, b}\right) = \left({a, b}\right)$.

Thus $\left({a, b}\right) \preceq \left({a, b}\right)$ and so $\preceq$ is reflexive.

$\Box$


Transitivity

Suppose $\left({a_1, b_1}\right) \preceq \left({a_2, b_2}\right) \preceq \left({a_3, b_3}\right)$.

Suppose $\left({a_3, b_3}\right) \prec \left({a_1, b_1}\right)$.

This would happen because:

  • $b_3 \prec_2 b_1$, which can't happen because $\preceq_2$ is transitive;
  • $b_3 = b_1$ and $a_3 \prec_1 a_1$, which can't happen because $\preceq_1$ is transitive.


So we have shown that $\left({a_1, b_1}\right) \preceq \left({a_3, b_3}\right)$ and so $\preceq$ is transitive.

$\Box$


Antisymmetry

Suppose $\left({a_1, b_1}\right) \preceq \left({a_2, b_2}\right) \preceq \left({a_1, b_1}\right)$.

Suppose $\left({a_1, b_1}\right) \ne \left({a_2, b_2}\right)$.

Then one of two cases holds:

  • $b_1 \ne b_2$, which can't happen because then either $\left({a_1, b_1}\right) \prec \left({a_2, b_2}\right)$ or $\left({a_2, b_2}\right) \prec \left({a_1, b_1}\right)$;
  • $b_1 = b_2$, and $a_1 \ne a_2$, which can't happen because then either $\left({a_1, b_1}\right) \prec \left({a_2, b_2}\right)$ or $\left({a_2, b_2}\right) \prec \left({a_1, b_1}\right)$.


Thus in all cases it can be seen that $\left({a_1, b_1}\right) \preceq \left({a_2, b_2}\right) \preceq \left({a_1, b_1}\right) \implies \left({a_1, b_1}\right) = \left({a_2, b_2}\right)$.

So $\preceq$ is antisymmetric.

$\Box$


So we have shown that:

$\preceq$ is connected
$\preceq$ is reflexive, transitive and antisymmetric.

Thus by definition, $\preceq$ is a total ordering and so $\left({S_1 \times S_2, \preceq}\right)$ is a toset.

$\blacksquare$


Sources