# Prove Partial Order

Prove that the following relation is an order on the Cartesian product {${1,2,3}$} × {${1,2,3}$} and draw its diagram.

$((x_1,x_2),(y_1,y_2))$ER if and only if $x_1 < x_2$ or $x_1=x_2$ and $y_1 ≤ y_2$

I can prove that this is reflexive, but I don't know how to prove it for anti-symmetricity and transivity.

-
For future reference, this is known as the lexicographical order. – Gerry Myerson Nov 12 '12 at 5:38
It is about 9 elements. Write them down all, preferaribly according to the given order, you can also skip the parenthesis and the comma, so that the elements of the cartesian product may now be written like: 11, 32, 13, 22, ... maybe that helps. – Berci Nov 12 '12 at 11:24

Presumably there's a typo in the question, otherwise the relation is neither antisymmetric nor transitive. Counterexamples:

• E.g. $\big((1,2),(2,3)\big) \in R$ since $1<2$, and $\big((2,3),(1,2)\big) \in R$ since $2<3$, and thus $R$ is not antisymmetric.

• E.g. $\big((1,1),(1,2)\big) \in R$ since $1=1$ and $1 \leq 2$, and $\big((1,2),(3,2)\big) \in R$ since $1<2$, but $\big((1,1),(3,2)\big) \not\in R$ since $1 \not< 1$ and $3 \not\leq 2$, and thus $R$ is not transitive.

This might explain why you are finding the question difficult.

Fixing the probable typo, the relation becomes:

$\big((x_1,x_2),(y_1,y_2)\big) \in R$ if and only if $x_1<y_1$ or $x_1=y_1$ and $x_2 \leq y_2$.

To show it's an order relation, we check:

• Reflexive: Since $x_1=x_1$ and $x_2 \leq x_2$, we know $\big((x_1,x_2),(x_1,x_2)\big) \in R$. Hence $R$ is reflexive.

• Antisymmetric: Suppose $\big((x_1,x_2),(y_1,y_2)\big), \big((y_1,y_2),(x_1,x_2)\big) \in R$. Then there are four possibilities: $$\begin{array}{c|c|c|} & x_1<y_1 & x_1=y_1 \text{ and } x_2 \leq y_2 \\ \hline y_1<x_1 & \text{impossible} & \text{impossible} \\ \hline y_1=x_1 \text{ and } y_2 \leq x_2 & \text{impossible} & \\ \hline \end{array}$$ So, we must have $x_1=y_1$ and $x_2 \leq y_2$ and $y_2 \leq x_2$. Since $\leq$ is an antisymmetric (order) relation, we must have that $x_2=y_2$. Hence $(x_1,x_2)=(y_1,y_2)$, and we can conclude that $R$ is antisymmetric.

• Transitive: Suppose $\big((x_1,x_2),(y_1,y_2)\big), \big((y_1,y_2),(z_1,z_2)\big) \in R$. Then there are four possibilities: $$\begin{array}{c|c|c|} & x_1<y_1 & x_1=y_1 \text{ and } x_2 \leq y_2 \\ \hline y_1<z_1 & \text{implies } x_1<z_1 & \text{implies } x_1<z_1 \\ \hline y_1=z_1 \text{ and } y_2 \leq z_2 & \text{implies } x_1<z_1 & \text{implies } x_1=z_1 \text{ and } x_2 \leq z_2 \\ \hline \end{array}$$ (The above deductions use the transitivity of the relations $=$, $<$ and $\leq$, along with the properties "$x_1=y_1<z_1$ implies $x_1<z_1$" and "$x_1<y_1=z_1$ implies $x_1<z_1$".) In all four cases, $\big((x_1,x_2),(z_1,z_2)\big)$ satisfies the conditions of $R$. Hence $\big((x_1,x_2),(z_1,z_2)\big) \in R$, and we can conclude that $R$ is transitive.

-