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.

  • 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 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 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 (The above deductions use the transitivity of the relations $=$, $<$ and $\leq$, along with the properties "$x_1=y_1 implies $x_1" and "$x_1 implies $x_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.