0
$\begingroup$

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.

  • 2
    For future reference, this is known as the *lexicographical order*.2012-11-12
  • 0
    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.2012-11-12

1 Answers 1

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

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

  • 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