# Transitive & symmetric relation; why is this wrong?

"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?

• You have $y R z$ and $z R y$, but not $y R y$. – user61527 Feb 5 '14 at 0:23
• 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? – H4x0rjax Feb 5 '14 at 0:25
• If you had all these relations, $R$ would be both transitive and reflexive. Currently, it's neither. – user61527 Feb 5 '14 at 0:27
• Right, but I specifically can't have reflexive. I need Transitive and symmetric for this problem. Sorry, I'm just confused. – H4x0rjax Feb 5 '14 at 0:29
• If this was transitive, since you have xRy and yRx, you would need to have xRx as well, but that would make it reflexive. – Bonnaduck Feb 5 '14 at 0:34

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?

• 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). – H4x0rjax Feb 5 '14 at 0:48
• 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... – Ross Millikan Feb 5 '14 at 0:51
• Then unfortunately I'm unable to see the suggested way out.. – H4x0rjax Feb 5 '14 at 0:55
• What would you need to take away from the relation you just gave to make sure it wasn't reflexive? – Bonnaduck Feb 5 '14 at 1:01
• @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\}$ – Ross Millikan Feb 5 '14 at 1:06

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!

• Thank you! It seems to me that there are very few cases where this will not be true, such as an empty relation.. – H4x0rjax Feb 5 '14 at 0:42
• Okay, is S the domain here? if so, is R just a set of mappings? what is the range? – H4x0rjax Feb 5 '14 at 0:44
• @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. – David Feb 5 '14 at 0:46