$$\begin{array}{l}{R_{1}=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}} \\ {R_{2}=\{(1,1),(2,2)\}} \\ {R_{3}=\{(1,2),(2,3),(3,1)\}}\end{array}$$

$$\begin{array}{l}{R_{4}=\{(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)\}} \\ {R_{5}=\{(1,1),(2,2),(3,3),(1,2),(2,3),(3,1)\}} \\ {R_{6}=\{(1,2),(2,1)\}}\end{array}$$

My answer

In order for $R_i$ to be an equivalence relation it should meet four criteria

  • $R_i$ should be a subset of $\{1,2,3\} \times \{1,2,3\}$
  • $R_i$ should be reflexive. symmetric and transitive.

My conclusion is that none of the relations above are an equivalence relation. But the answer key is $R_1$. The problem is that $3$ is not related to any of the others and one cannot see that $R_1$ is transitive.

Q1: Why am I wrong? Q2: Why isn't $R_5$ an equivalence relation?


For transitivity you need for all $a,b,c\in \{1,2,3\}$: If $a$ is related to $b$ and $b$ is related to $c$, then $a$ is related to $c$. You can indeed check for $R_{1}$ that this is true, since if you pick $a = 3$, then the statement is trivial. Since it only satisfies the "if" condition if you pick $b = 3$, since $3$ is only related to $3$.

Clarification: The thing you have to check for transitivity is for every $(a,b) $ and $(b,c)$ in $R_{1}$ you also have $(a,c)$ in $R_{1}$. Maybe this way of phrasing transitivity helps you to understand it better.

  • $\begingroup$ I do not understand. I can't really pinpoint what it is that I do not understand sorry. Also, why is $R_5$ not a relation of equivalence? $\endgroup$ – Xenusi Nov 3 '19 at 19:55
  • $\begingroup$ $R_5$ is not symmetric. (1,2) is in there but (2,1) is not $\endgroup$ – Zeno Nov 3 '19 at 20:16

$R_2$ is not reflexive since you don't have $(3,3)$.

$R_3$ is not reflexive.

$R_4$ is not reflexive since we haven't $(1,1)$.

$R_5$ is not transitive because you have $(1,2),(2,3)$ but not $ (1,3)$.

$R_6$ is not reflexive.

$R_1$ is an equivalence relation.

  • $\begingroup$ @MatthewDaly Why is that? Is it because $R_2$ is not a function? $\endgroup$ – Xenusi Nov 3 '19 at 19:59
  • $\begingroup$ @Xenusi $R_2$ is reflexive at $\{1,2\}$ not at $\{1,2,3\}$. $\endgroup$ – hamam_Abdallah Nov 3 '19 at 20:04

The definition of transitivity is a one-way conditional, if-then statement:

If $aRb$* and $bRc$, Then (but not only then) $aRc$, for all $a,b,c$ in the set.

For $R_1$, we have $1R_12$ and $2R_11$, so we must have $1R_11$ and $2R_12$, which we do. Since $3$ does not relate to anything but itself, "all" the existence of $3R_13$ does is allow us to say $R_1$ is reflexive.

For $R_5$, we have $1R_52$ and $2R_53$, so we must have $1R_53$, which we do not. This alone is enough to tell us that $R_5$ is not transitive, because we don't have it for all $a,b,c$ in $\{1,2,3\}$. (It also happens to be not symmetric, but that's irrelevant for our discussion at this point.)

*The $aRb$ notation is a common shorthand when discussing relations, reminiscent of $a=b$ or $a<b$. Basically, $aRb$ means $(a,b)$ is in $R$.

  • $\begingroup$ So either we have it for all or none? $\endgroup$ – Xenusi Nov 3 '19 at 20:43
  • $\begingroup$ All or none of what? $\endgroup$ – No Name Nov 3 '19 at 20:47
  • $\begingroup$ So either we have it for all or none: Transivity $\endgroup$ – Xenusi Nov 3 '19 at 20:50
  • $\begingroup$ No, either we have "it" for all (and are therefore transitive) or not one (and are therefore not transitive). Having "it" for none (i.e., not any) is more specific (antitransitive). $\endgroup$ – No Name Nov 3 '19 at 21:06

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.