Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
add comment

1 Answer 1

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.