# How to find efficient not transitive pairs in relations? (Discrete math)

I'm doing at the moment some math and struggle with the following.

So there are relations and they can or can not hol specific properties. Most common are described reflexive, symmetric and transitive.

I know how they are defined, how they come together and analyse relations due that. But what I'm really strugglign with are finding pairs which ARE NOT transitive from equivalence relations. So, xRy, yRz, then xRz. Thats transitiviy.

But as soon as I got some equi. relation in set notation I rather struggle with checking the relation on the transitive property. Do you guys have any ideas how to proceed from here to make life easier for me? How do I find rather fast a pair xRz which isn't in the relation?

• Can you give some more information? Where does the relation come from? – Loreno Heer Jan 19 '15 at 23:31
• Um, I can give you some examples. But it wouldn't really help me since I got the same issue with different more complicated relations. It's more about getting a grasp how to tackle the exercises. For example, R = {(x,y) € IR^2| x^2 > x ^ y^2 > y} I wouldn't know where I should begin to find an pair which is NOT in the relation. :( – epomia Jan 19 '15 at 23:34

Let’s look at the example in your comment:

$$R=\left\{\langle x,y\rangle\in\Bbb R^2:x^2>x\land y^2>y\right\}\;.$$

The defining condition involves the relationship $x^2>x$ for real numbers $x$, so a good place to begin is by figuring which $x\in\Bbb R$ have this property. In other words, solve the inequality $x^2>x$. You may know the solution right away; if not, rewrite it as $x^2-x>0$ and factor to get $x(x-1)>0$, which is true when $x<0$ or $x>1$. Thus,

$$R=\left\{\langle x,y\rangle:(x<0\text{ or }x>1)\land(y<0\text{ or }y>1)\right\}\;.$$

This is a pretty simple description: each $\langle x,y\rangle$ falls into one of four categories:

• $x<0$ and $y<0$;
• $x<0$ and $y>1$;
• $x>1$ and $y<0$; or
• $x>1$ and $y>1$.

It might even help at this point to sketch the graph of $R$, shading the four regions of the plane that are in $R$.

Now let’s investigate the transitivity of $R$. Suppose that $\langle x,y\rangle\in R$ and $\langle y,z\rangle\in R$. If worse comes to worst, we can simply examine the possible cases.

• Suppose that $x<0$ and $y<0$. Then since $\langle y,z\rangle\in R$, either $z<0$ or $z>1$, and in either case $\langle x,z\rangle\in R$.

• Suppose that $x<0$ and $y>1$. Then since $\langle y,z\rangle\in R$, either $z<0$ or $z>1$, and in either case $\langle x,z\rangle\in R$.

I could continue through the remaining two cases, but take a closer look at the first two: in both cases the mere fact that $\langle y,z\rangle\in R$ told me — without any specific information about $x$ or $y$ — that either $z<0$ or $z>1$. Similarly, the mere fact that $\langle x,y\rangle\in R$ tells me — again without any specific information about the other two real numbers involved — that either $x<0$ or $x>1$. But then $x$ and $z$ necessarily fall into one of the four categories, and I know for sure that $\langle x,z\rangle\in R$. In short, I’ve just proved that this $R$ is transitive.

The best general advice that I can give is to dig into the definition of the relation to get an idea of just how it works. Sometimes that’s best done by analyzing the definition itself, perhaps breaking it into cases as I did here. Sometimes it’s best done by checking a fairly representative variety of examples. If none of that gives you any insight into whether a relation is transitive or not, it may be worth trying to prove that it is: with a bit of luck either you will succeed, or you’ll run into some obstacle that points the way towards a counterexample showing that the relation actually isn’t transitive.

As an example, consider the relation

$$S=\{\langle x,y\rangle\in\Bbb R^2:|x-y|\le 1\}\;.$$

You could solve the inequality $|x-y|\le 1$: $-1\le x-y\le 1$, so $y-1\le x\le y+1$, and hence $x-1\le y\le x+1$. This is easy to graph, and the graph can be a helpful tool. However, I want instead to use $S$ to illustrate the idea of trying to prove transitivity and seeing what goes wrong.

Suppose, then, that $\langle x,y\rangle\in S$ and $\langle y,z\rangle\in S$. This of course simply means that $|x-y|\le 1$ and $|y-z|\le 1$. To prove that $S$ is transitive, we’d have to prove that $|x-z|\le 1$. About the only possible tool that comes to mind is the triangle inequality:

$$|x-z|=|(x-y)+(y-z)|\overset{(*)}\le|x-y|+|y-z|\le 2\;.$$

That’s not good enough. Moreover, if you’re familiar with the triangle inequality, you know that there are cases in which the inequality $(*)$ is actually an equality. This suggests that we should look for a counterexample to transitivity and even gives an idea of where we might find it: we might look for $x,y$, and $z$ such that $|x-y|=1$, $|y-z|=1$, and $|x-z|=2$. And that’s easy: take $x=0,y=1$, and $z=2$.

It’s always going to come down in the end to dealing with the specific relation confronting you, but perhaps I’ve at least given you some general ideas on how to try to proceed.