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

Question

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

Answer 1

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.

Answer 2

$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.

Answer 3

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$.