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
    How do you know that such an $R$ exists?2011-11-30
  • 0
    yes. i got a tip to check $$A \times A - Ia$$ but it didn't help2011-11-30
  • 0
    Yes is not an answer to my question.2011-11-30
  • 0
    oh sorry that is given that such R exists2011-11-30
  • 0
    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?2011-11-30
  • 0
    R is NOT transitive! sorry :(2011-11-30
  • 0
    And how sure are you that you don't want the union to be transitive instead of not transitive?2011-11-30
  • 0
    100% or that would be very easy.2011-11-30
  • 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
    oh crap! how could I not realize that! thanks!2011-11-30
  • 0
    @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.2011-11-30
  • 0
    I had this example, unfortunetly I mentally blocked that {(1,2) (2,1)} is not transitive2011-11-30
  • 0
    @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.)2011-11-30
  • 0
    what is a three circle? my course is in hebrew so I have big troubles with translation..2011-11-30
  • 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