Find the number of equivalence relations on set A = {1, 2, 3} such that (1,2) and (2,1) are elements of that relation.

Question

I first found the number of equivalence relations. It came out to be 5. Out of those 5 relations, how am I supposed to find the relations containing (1,2) and (2,1) without writing each relation out?

Answer 1

There is a one-to-one relation between equivalence relations on a set $A$ and partitions of the set $A$.

The equivalence relation is connected with the partition of its equivalence classes.

Conversely a partition $\mathcal P$ on $A$ is connected with the equivalence relation $R$ on $A$ determined by: $$aRb\iff\exists P\in\mathcal P\;[a,b\in P]$$

So the number of equivalence relations on $A=\{1,2,3\}$ that contain $(1,2)$ (and automatically $(2,1)$) equals the number of partitions $\mathcal P$ of $A$ with the property that $\exists P\in\mathcal P\;[1,2\in P]$.

There are $2$ such partitions of $A=\{1,2,3\}$:

• $\mathcal P_1=\{\{1,2\},\{3\}\}$
• $\mathcal P_2=\{\{1,2,3\}\}$

Also note that there are $5$ partitions of $A=\{1,2,3\}$ in total, indicating that your calculation of the total number of equivalence relations on $A$ is correct.