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.

$\endgroup$
  • $\begingroup$ How do you know that such an $R$ exists? $\endgroup$ – Phira Nov 30 '11 at 10:14
  • $\begingroup$ yes. i got a tip to check $$A \times A - Ia$$ but it didn't help $\endgroup$ – Nahum Nov 30 '11 at 10:18
  • $\begingroup$ Yes is not an answer to my question. $\endgroup$ – Phira Nov 30 '11 at 10:21
  • $\begingroup$ oh sorry that is given that such R exists $\endgroup$ – Nahum Nov 30 '11 at 10:22
  • $\begingroup$ 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? $\endgroup$ – Phira Nov 30 '11 at 10:25
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ oh crap! how could I not realize that! thanks! $\endgroup$ – Nahum Nov 30 '11 at 11:07
  • $\begingroup$ @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. $\endgroup$ – Martin Sleziak Nov 30 '11 at 11:15
  • $\begingroup$ I had this example, unfortunetly I mentally blocked that {(1,2) (2,1)} is not transitive $\endgroup$ – Nahum Nov 30 '11 at 11:34
  • $\begingroup$ @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.) $\endgroup$ – Martin Sleziak Nov 30 '11 at 11:41
  • $\begingroup$ what is a three circle? my course is in hebrew so I have big troubles with translation.. $\endgroup$ – Nahum Nov 30 '11 at 11:44
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ edge from 1 to 2 is transitive and the edge suqared is is the empty set so their union is transitive as well $\endgroup$ – Nahum Nov 30 '11 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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