Reflexive, symmetrical but not transitive

Question

I am supposed to create a relation R on a set $X = \{a,b,c,d\}$ that is reflexive, symmetrical but not transitive.

My attempt looks like this: $R = \{(a,a),(b,b),(c,c),(d,d),(a,b)(b,a),(b,c),(c,b),(c,d)(d,c)\}$

I believe my current solution works - but I have also been presented with a minimal solution, which would look like this:

$R = \{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(b,c),(c,b)\}$

It reflexive since $(a,a),(b,b),(c,c),(d,d)\in R$.

I can also see that it is not transitive, since $(a,b) \in R$ and $(b,c) \in R $ but there is no $(a,c) \in R $.

But is it symmetrical?

The defintion of a symmetrical relationship is as follows:

$\forall x \forall y$ $xRy \implies yRx $

I thought that since the element $d \in X$, I would have to include something like $(d,c)$ and $(c,d)$ in R, in order for it to actually be symmetrical. I interpret the $\forall x \forall y $ as all elements in X, am I missing something really obvious here?

Is it perhaps that $(d,d)\in R$ and if we were to look at $x=d$ and $y=d$, we do in fact have a $xRy \implies yRx$ ?

Answer 1

I think you're misreading how the quantifiers interact with the implication in the definition of symmetry.

Requiring that $\forall x\forall y(xRy\Rightarrow yRx)$ is the same as requiring that all of these 16 instances must be true: $$ \begin{array}{cccc} aRa \Rightarrow aRa, & aRb \Rightarrow bRa, & aRc \Rightarrow cRa, & aRd \Rightarrow dRa, \\ bRa \Rightarrow aRb, & bRb \Rightarrow bRb, & bRc \Rightarrow cRb, & bRd \Rightarrow dRb, \\ cRa \Rightarrow aRc, & cRb \Rightarrow bRc, & cRc \Rightarrow cRc, & cRd \Rightarrow dRc, \\ dRa \Rightarrow aRd, & dRb \Rightarrow bRd, & dRc \Rightarrow cRd, & dRd \Rightarrow dRd \\ \end{array}$$

In both of the examples you present, some of these -- such as $aRb\Rightarrow bRa$ -- are true because both sides of the $\Rightarrow$ are true. Others, such as $dRb\Rightarrow bRd$ are true because both sides are false, which is a perfectly good way for a $\Rightarrow$ to be true.

The difference between your example and the minimal example is just that $dRc\Rightarrow cRd$ and $cRd\Rightarrow dRc$ are true for one reason in your example and true for another reason in the minimal example. They're true all the same.

Answer 2

To be symettric if $(d,c)$ is included than $(c,d)$ must also be included. But there is absolutely no reason $(d,c)$ need to be included$.

To have a minimum relationship that is not transitive you need:

Wolog: $(a,b)$ and $(b,c)$ but not $(a,c)$.

To be reflexive you need. $(a,a), (b,b), (c,c), (d,d)$.

Since you have $(a,b)$ and $(b,c)$ you need $(b,a)$ and $(c,b)$. You also need $(a,a), (b,b), (c,c),(d,d)$ but those are "self-symmetric" so to speak and we already listed them.

so $(a,a)(b,b)(c,c)(a,b)(b,a),(a,c),(c,a),(d,d)$ is reflexive symmetric and not reflexive and minimal.

Now if we threw in any $(d,x)$ we would have to throw in $(x,d)$ but there is utterly no reason we have to throw in any $(d,x); d\ne x$.

Perhaps it would make things clear if we point out the ONLY reason we had to toss it $(a,b)$ in the first place was so that it couldn't be transitive. If we don't have any $(x,y); x\ne y$ we can't have any $(x,y), (y,z)$ but not $(x,z)$.

If the problem was find a relationship that was reflexive and symmetric and we don't care whether it is or is not transitive, the minimal would be $\{(a,a),(b,b), (c,c),(d,d)\}$.

It's reflexive: $(x,x)$ is included for all $x$.

It's symmetric: If $(x,y)$ is included so is $(y,x)$.

But it is also transitive.

To not be transitive we need $(x,y)$ and $(y,z)$ without $(x,z)$. (So $x\ne z$ as $(x,x)$ is included. ANd $z \ne y$ as $(x,y)$ is included and $x \ne y$ as $(y,z)$ is included.) But we don't need any more.