Is my transitivity proof correct for the relation over $\mathbb{Z} \times \mathbb{Z}$ where $(a,b)R(c,d) \iff (a \le c \lor b \le d)$?

Question

I'm having a hard time developing abstract thinking to solve problems regarding a relation's properties. I've spend quite an absurd amount of time on this one, but I think I finally grasped a bit of the general idea. However, my solution feels a bit fishy, or informal. Can you take a look at it? Is it correct? Any feedback is greatly appreciated.

For $A = \mathbb{Z} \times \mathbb{Z}$, is defined the relation $R$ over $A$ where $(a,b)R(c,d) \iff (a \le c \lor b \le d)$. Determine whether the relation $R$ is transitive.

It seems quite likely that it is transitive.

We need to prove that $(a,b)R(c,d) \land (c,d)R(e,f) \implies (a,b)R(e,f)$

First, $(a,b)R(c,d)$ means that either $a \le c$ or $b \le d$.

Next, $(c,d)R(e,f)$ means that either $c \le e$ or $d \le f$.

Using the premise, we can conclude that these four cases occur:

• $a \le c \land c \le e$

• $a \le c \land d \le f$

• $b \le d \land c \le e$

• $b \le d \land d \le f$

All four are true, according to the premise. Let's pick up the first one:

$$a \le c \land c \le e$$

Is equivalent to

$$a \le e$$

Which is enough to prove that $(a,b)R(e,f)$.

---

As you can see, I just generated some combinations using the premise and one of them happened to be useful. This doesn't sound quite pretty. How can I improve this solution?

Answer 1

Using the premise, we can conclude that these four cases occur:

• $a \le c \land c \le e$
• $a \le c \land d \le f$
• $b \le d \land c \le e$
• $b \le d \land d \le f$

All four are true, according to the premise.

No, at least one is true. If the first or the fourth is true, you’re in business, but what if only the second is true? Is that possible?

Yes, it is. For example, $\langle 1,2\rangle\mathbin{R}\langle 1,1\rangle$ and $\langle 1,1\rangle\mathbin{R}\langle 0,1\rangle$, but ... ?

For this relation you may find it helpful to think graphically. Each pair $\langle a,b\rangle\in\Bbb N\times\Bbb N$ corresponds to a point in the plane. $\langle a,b\rangle\mathbin{R}\langle c,d\rangle$ if and only if either

• $a\le c$, in which case the point $\langle a,b\rangle$ is not to the right of the point $\langle c,d\rangle$, or
• $b\le d$, in which case the point $\langle a,b\rangle$ is not above the point $\langle c,d\rangle$.

In my counterexample $\langle 1,2\rangle$ is not to the right of $\langle 1,1\rangle$, which is not above $\langle 0,1\rangle$, but $\langle 1,2\rangle$ is both to the right of and above $\langle 0,1\rangle$.

Answer 2

$(2,2)R(3,0)$ and $(3,0)R(1,1)$ but $(2,2)R(1,1)$ is not true. If you change $\vee$ with $\land$, then it would be transitive.