1
$\begingroup$

"Give a relation that satifies the condition:"

Symmetric and transitive but not reflexive.

This is what I gave:

R = {(x,y), (y,z), (z,x), (y,x), (z,y), (x,z)}

I was told this was not transitive. However, my book's definition of transitive is the following:

R is transitive if for every x, y, and z, xRy and yRz implies xRz

What did I do incorrectly?

$\endgroup$
  • 2
    $\begingroup$ You have $y R z$ and $z R y$, but not $y R y$. $\endgroup$ – user61527 Feb 5 '14 at 0:23
  • 1
    $\begingroup$ I also have xRy and yRx, but no xRx... and zRx xRz, but not zRz. I assumed those are considered reflexive.. Would I need those as well? $\endgroup$ – H4x0rjax Feb 5 '14 at 0:25
  • $\begingroup$ If you had all these relations, $R$ would be both transitive and reflexive. Currently, it's neither. $\endgroup$ – user61527 Feb 5 '14 at 0:27
  • $\begingroup$ Right, but I specifically can't have reflexive. I need Transitive and symmetric for this problem. Sorry, I'm just confused. $\endgroup$ – H4x0rjax Feb 5 '14 at 0:29
  • $\begingroup$ If this was transitive, since you have xRy and yRx, you would need to have xRx as well, but that would make it reflexive. $\endgroup$ – Bonnaduck Feb 5 '14 at 0:34
0
$\begingroup$

Let us use $\{a,b,c\}$ as the set your relation is over to avoid confusion with the $x,y,z$ in the definitions of reflexive, symmetric, transitive. To be reflexive you would have to have $\{(a,a),(b,b),(c,c)\} \subset R$ Your relation corresponds to $\{(a,b),(b,a),(a,c)(c,a),(b,c),(c,b)\}$ so your relation is certainly not reflexive. In the definition of transitive, it is not required that $x,y,z$ be distinct elements, so I can say that if the relation is transitive $(aRb\ \& \ bRa) \implies aRa$. By inspection this is false, so the relation is not transitive.

To rescue this, assume $aRb$. Then by symmetry you have $bRa$. By transitivity, then we need $aRa$ Does this suggest a way out?

$\endgroup$
  • $\begingroup$ Is this a possible solution? R= {(a,b), (b, a), (a, a)} It would seem to me this satisfies symmetric and transitive, but not reflexive as there is no (b,b). $\endgroup$ – H4x0rjax Feb 5 '14 at 0:48
  • $\begingroup$ No, because $(bRa\ \&\ aRb) \implies bRb$ so it is not transitive. If you add $(b,b)$ to it you will be fine because you still don't have $(c,c)$. But there is a simpler example... $\endgroup$ – Ross Millikan Feb 5 '14 at 0:51
  • $\begingroup$ Then unfortunately I'm unable to see the suggested way out.. $\endgroup$ – H4x0rjax Feb 5 '14 at 0:55
  • $\begingroup$ What would you need to take away from the relation you just gave to make sure it wasn't reflexive? $\endgroup$ – Bonnaduck Feb 5 '14 at 1:01
  • $\begingroup$ @Bonnaduck: His relation, augmented by the required $(b,b)$ is still not reflexive. In fact, that is an acceptable answer to the problem if the set the relation applies to is $\{a,b,c\}$ $\endgroup$ – Ross Millikan Feb 5 '14 at 1:06
2
$\begingroup$

At the risk of confusing you even more, here is a well known fake theorem.

"Theorem". If a relation is symmetric and transitive, it must be reflexive.

"Proof". Suppose $R$ is symmetric and transitive. Take any element $x$. Take an element $y$ such that $x\,R\,y$. Since $R$ is symmetric we have $y\,R\,x$. But then since $R$ is transitive and $x\,R\,y$ and $y\,R\,x$, we have $x\,R\,x$. As this is true for all $x$, the relation $R$ is reflexive.

If you can figure out what is wrong with this argument, it may guide you in the direction of the example you need. Good luck!

$\endgroup$
  • $\begingroup$ Thank you! It seems to me that there are very few cases where this will not be true, such as an empty relation.. $\endgroup$ – H4x0rjax Feb 5 '14 at 0:42
  • $\begingroup$ Okay, is S the domain here? if so, is R just a set of mappings? what is the range? $\endgroup$ – H4x0rjax Feb 5 '14 at 0:44
  • $\begingroup$ @user3221706, well done - the empty relation is an answer (not the only example) - it is symmetric and transitive, though you will probably have to think carefully to see why. $\endgroup$ – David Feb 5 '14 at 0:46

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.