Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers

up vote 0 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.