# Which of the following relations on $\{1,2,3\}$ is an equivalence relation?

$$\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}$$

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.

• 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? – Xenusi Nov 3 '19 at 19:55
• $R_5$ is not symmetric. (1,2) is in there but (2,1) is not – 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.

• @MatthewDaly Why is that? Is it because $R_2$ is not a function? – Xenusi Nov 3 '19 at 19:59
• @Xenusi $R_2$ is reflexive at $\{1,2\}$ not at $\{1,2,3\}$. – 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. Basically, $$aRb$$ means $$(a,b)$$ is in $$R$$.

• So either we have it for all or none? – Xenusi Nov 3 '19 at 20:43
• All or none of what? – No Name Nov 3 '19 at 20:47
• So either we have it for all or none: Transivity – Xenusi Nov 3 '19 at 20:50
• 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). – No Name Nov 3 '19 at 21:06