Identifying Equivalence Relations - Foundations of Mathematics

Question

Let $S =\{1,2,3\}$. Each of the following subsets of $ S\times S$ gives a relation on $S$. Which of the following give equivalence relations on $S$?:

(a) $\{(1,1),(1,2),(2,1),(2,2),(3,2),(3,3)\}$

(b) $\{(1,1)\}$

(c) $\{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2)\}$

(d) $\{(1,1),(1,3),(2,2),(2,3),(3,1),(3,2),(3,3)\}$

---

Well, I know that a relation is a subset, $R$ of $S\times S$ and the elements of $R$ are ordered in pairs $(x,y)$, where $x$ and $y$ are in $S$. $x\sim y$ shows that the ordered pair $(x,y)$ is in the subset $R$. Also, an equivalence relation means that the relation is reflexive, symmetric and transitive. Thus, I thought that the answer would be none of the above - but, this was not an option in the question, so I must have gotten something confused somewhere along the way. Any help would be appreciated, thanks!

Answer 1

As written, you are correct. None of the given relations are equivalence relations. There are potentially multiple reasons why each are not equivalence relations, but here are a few:

• In (a) we have $(3,2)$ and $(2,1)$ both in the relation but $(3,1)$ is not so it fails transitivity
• In (b) we do not have $(2,2)$ in the relation, so it is not reflexive. (The relation $\{(1,1)\}$ is an equivalence relation on the set $\{1\}$, but it is not an equivalence relation on the set $\{1,2,3\}$)
• In (c) we do not have $(3,3)$ in the relation, so it is not reflexive
• In (d) we have $(1,3)$ and $(3,2)$ both in the relation but $(1,2)$ is not so it fails transitivity