0
$\begingroup$

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.

  • 0
    The other thing is also very easy, there are not that many distinct relations.2011-11-30

2 Answers 2

0

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.)

  • 0
    @Nahum I believe Phira meant something like 1->2->3->1, which is precisely the visualization of the relation {(1,2),(2,3),(3,1)}, which was suggested in my answer.2011-11-30
1

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.

  • 0
    edge from 1 to 2 is transitive and the edge suqared is is the empty set so their union is transitive as well2011-11-30