# Finding a untransitive relation

I have tried without luck for a few hours now...

given $$A=\{1,2,3\}$$ find $R \subseteq A \times A$ such that $R \cup R^2$ is not transitive.

-
How do you know that such an $R$ exists? –  Phira Nov 30 '11 at 10:14
yes. i got a tip to check $$A \times A - Ia$$ but it didn't help –  Nahum Litvin Nov 30 '11 at 10:18
Yes is not an answer to my question. –  Phira Nov 30 '11 at 10:21
oh sorry that is given that such R exists –  Nahum Litvin Nov 30 '11 at 10:22
Your title seems to imply that $R$ has to be transitive, but the body of your question and the tip seems to imply that it is not. So which is it? –  Phira Nov 30 '11 at 10:25
show 4 more comments

What about $R=\{(1,2),(2,3),(3,1)\}$.

Then $R^2=\{(1,3),(2,1),(3,1)\}$, which implies $$S=R\cup R^2= \{(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)\}.$$

The relation $S$ is not transitive since $(1,2),(2,1)\in S$ but $(1,1)\notin S$.

Let me explain how it is possible to come up with such examples.

You can visualize relations as arrow between elements of the sets. A pair $(x,y)$ is in $R^2$ if there is path of length 2 between $x$ and $y$. Thus $S=R\cup R^2$ contains all pairs joined by a path of length at most 2. Every transitive relation containing $S$ must contain all pairs for paths of lengths 3 and 4. So I was trying to construct a relation such that I have 2 elements joined by a path of length 3, but there is no path of length 2 between them.

The same thing explained a bit differently.

Lemma. A relation $S$ is transitive if and only if $S\circ S\subseteq S$.

Maybe you had this result on your lectures. You can find the proof e.g. at proofwiki.

If we use it for your case, we have $$S\circ S=(R\cup R^2)\circ (R\cup R^2) = R^2 \cup R^3\cup R^4.$$ This implies $S\circ S\setminus S= R^3\cup R^4 \setminus (R^2\cup R)$. So if I am able to find a relation such that $R^3\setminus (R^2\cup R)$ is non-empty, this will give a counterexample. (And this is basically looking for two elements such that the shortest path has length 3, as I explained above.)

-
oh crap! how could I not realize that! thanks! –  Nahum Litvin Nov 30 '11 at 11:07
@Nahum: I've added and explanation showing how to come up with such examples. I tried to explaining how one could visualize $R^2$ and composition of relations. Maybe this could help you, too. –  Martin Sleziak Nov 30 '11 at 11:15
I had this example, unfortunetly I mentally blocked that {(1,2) (2,1)} is not transitive –  Nahum Litvin Nov 30 '11 at 11:34
@Nahum Only now I noticed that Phira's answer suggest three-circle (I would call it three-cycle, but it doesn't matter). So it is exactly the same example as mine. (I did not read that answer too carefully, since I when I briefly glanced over it, I thought that this answer works with the assumption that $R$ is transitive.) –  Martin Sleziak Nov 30 '11 at 11:41
what is a three circle? my course is in hebrew so I have big troubles with translation.. –  Nahum Litvin Nov 30 '11 at 11:44
show 1 more comment

If $R$ is transitive, then $R^2$ is a subset of $R$, so the union is transitive.

Therefore, $R$ cannot be chosen transitive.

If you don't have this condition, you can take a three-circle.

-
edge from 1 to 2 is transitive and the edge suqared is is the empty set so their union is transitive as well –  Nahum Litvin Nov 30 '11 at 10:39