Proving a transitive and antisymmetric relation

Question

Define a relation $\triangleleft$ on Z x Z by $(c,d) \triangleleft (e,f)$ if and only if either $c < e$ or else $c = e$ and $d \leq f$
Prove that $\triangleleft$ is transitive and antisymmetric.

Hi all,
I'm extremely confused on how to approach this proof. So far I understand how to start the proof by stating that c, d, e, f $\in$ Z. Please help! Thank you kindly.

Answer 1

The definitions of antisymmetric and transitive relations:

$\bullet$ A relation $\mathcal R \subseteq A^2$ is antisymmetric iff for all $x,y\in A$; $(x,y) \in \mathcal R$ and $x\neq y$ implies $(y,x) \not\in \mathcal R$.
$\bullet$ A relation $\mathcal R \subseteq A^2$ is transitive iff for all $x,y,z\in A$; $(x,y) \in \mathcal R$ and $(y,z) \in \mathcal R$ implies $(x,z) \in \mathcal R$.

I will show you how to prove that $\triangleleft$ is antisymmetric.

First, define $x=(x_1,x_2)$ and $y=(y_1,y_2)$ and assume $x\neq y$, $x \triangleleft y$.

$x \triangleleft y$ is equivalent with $$x_1<y_1 \vee (x_1=y_1 \wedge x_2 \leq y_2) \tag1$$ We are trying to prove that $\neg(y \triangleleft x)$. Let's see what $y\triangleleft x$ means. It is equivalent with $$y_1<x_1 \vee (y_1=x_1 \wedge y_2 \leq x_2) \tag2$$

Let's break the disjunction in $(1)$ into two parts:

1. Suppose $x_1<y_1$. It directly follows that both $y_1<x_1$ and $y_1=x_1$ are false. Therefore, $(2)$ cannot be true.
2. Suppose $x_1=y_1 \wedge x_2\le y_2$. Again, $y_1<x_1$ is false, so we need $y_2\le x_2$ to be true. Because $x_2\le y_2$, we know that $y_2<x_2$ is not true, but this still allows for the possibility that $x_2=y_2$. But this is also false because $x_1=y_1$ and we have assumed $x \ne y$.

You can see that in both cases we have shown that the premise $x\ne y$ and $x \triangleleft y$ implies $\neg(y \triangleleft x)$, therefore $\triangleleft$ is an antisymmetric relation. An alternative proof would be to introduce the appropriate symbols and show that the previous implication reduces to $\bot$ using Boolean algebra.

Try to prove that the relation is transitive by yourself, using the information I provided. Good luck!