\problemdata
{partial order}
{S00 ps3}

% topic: relations, posets
% source: Velleman 4.4.4

\begin{problem}
Suppose $R$ is a partial order on $A$ and $S$ is a partial order on $B$.  
Define a relation $T$ on $A \times B$ as follows: $T = \{((a, b), (a', b')) \in
(A \times B) \times (A \times B) \mid aRa' \mbox{ and } bSb'\}$.  Show that $T$ is a partial
order on $A \times B$.  If both $R$ and $S$ are total orders, will $T$ also be 
a total order?

\solution{
\newline
To show $T$ is a poset on $A \times B$, we must show it is reflexive, 
symmetric, and transitive on $A \times B$.
\newline
\emph{Reflexive:} Choose an arbitrary element of $A \times B$, if one exists
(if none exists, there's nothing to prove and $T$ is reflexive).  Call this
element $(x, y)$.  To prove $T$ is reflexive, we must prove $((x, y)T(x, y))$.
Given we have $(x, y)$ chosen, we know $xRx$ and $ySy$ as both $R$ and $S$ 
are reflexive.  Thus, by the definition of $T$, $((x, y), (x, y)) \in T$ as
it is an element of $(A \times B) \times (A \times B)$ such that $xRx \land
ySy$.  Therefore, $T$ is reflexive.
\newline
\emph{Antisymmetric:} We must show that $\forall (a, b) \in (A \times B) \;
\forall (c, d) \in (A \times B) \; 
(((a, b)T(c, d) \land (c, d)T(a, b)) \implies (a, b) = (c, d))$.  Suppose 
we choose an arbitrary $a \in A$, $b \in B$, $c \in A$, and $d \in B$ such 
that the above premise holds.  If no such elements exist, $T$ is trivially
antisymmetric.  We have that $aRc \land cRa$ from the definition of $T$,
and thus $a = c$ as $R$ is antisymmetric.  Furthermore, $b = d$ by similar
rationale.  Thus, $(a, b) = (c, d)$, as needed.  $T$ is antisymmetric.
\newline
\emph{Transitive:} We must show that $\forall (a, b) \in (A \times B) \; 
\forall (c, d) \in (A \times B) \; \forall (e, f) \in (A \times B) \; 
(((a, b)T(c, d) \land (c, d)T(e, f)) \implies (a, b)T(e, f))$.  Let's 
arbitrarily choose a particular $a \in A$, $b \in B$, $c \in A$, $d \in B$, 
$e \in A$, and $f \in B$ such that the premise of the above implication holds. 
If there are no such elements, there is nothing to prove and $T$ is transitive.
We know that since $aRc$ and $cRe$ (by the definition of $T$), $aRe$ (by the
definition of $R$ being transitive).  Similarly, $bSf$ as $S$ is transitive.  
But since $aRe \land bSf$, $((a, b), (e, f)) \in T$ by the definition of $T$. 
Therefore, $T$ is transitive.
\newline
\textbf{No, $T$ is not a total order.}  Suppose you have $R = 
\{(a, a), (a, b), (b, b)\}$ (lexicographically less than or equal to) and 
$S = \{(1, 1), (1, 2), (2, 2)\}$ (numerically less than or equal to).  Then 
if we form $T$ as defined, there is no way to compare the points $(b, 1)$
and $(a, 2)$.
\newline
%\emph{A picture here would be nice!!!}
}
\end{problem}