Mohit Sinha 17th Mar, 2020

A relation is an equivalence relation if it is reflexive, transitive and symmetric.

Any equivalence relation RR on {1,2,3}{1,2,3}

1. must contain (1,1),(2,2),(3,3)(1,1),(2,2),(3,3)
2. must satisfy: if (x,y)∈R(x,y)∈R then (y,x)∈R(y,x)∈R
3. must satisfy: if (x,y)∈R,(y,z)∈R(x,y)∈R,(y,z)∈R then (x,z)∈R(x,z)∈R

Since (1,1),(2,2),(3,3)(1,1),(2,2),(3,3) must be there is RR , we now need to look at the remaining pairs (1,2),(2,1),(2,3),(3,2),(1,3),(3,1)(1,2),(2,1),(2,3),(3,2),(1,3),(3,1) . By symmetry, we just need to count the number of ways in which we can use the pairs (1,2),(2,3),(1,3)(1,2),(2,3),(1,3) to construct equivalence relations. This is because if (1,2)(1,2) is in the relation then (2,1)(2,1) must be there in the relation.

Notice that the relation will be an equivalence relation if we use none of these pairs (1,2),(2,3),(1,3)(1,2),(2,3),(1,3) . There is only one such relation:

• {(1,1),(2,2),(3,3)}{(1,1),(2,2),(3,3)}

or we use exactly one pair from (1,2),(2,3),(1,3)(1,2),(2,3),(1,3) . In this case, we can have three possible equivalence relations:

• {(1,1),(2,2),(3,3),(1,2),(2,1)}{(1,1),(2,2),(3,3),(1,2),(2,1)}
• {(1,1),(2,2),(3,3),(1,3),(3,1)}{(1,1),(2,2),(3,3),(1,3),(3,1)}
• {(1,1),(2,2),(3,3),(2,3),(3,2)}{(1,1),(2,2),(3,3),(2,3),(3,2)}

or when we use all all three pairs (1,2),(2,3),(1,3)(1,2),(2,3),(1,3) to get the following relation:

• {(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)}{(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)}

We can’t pick just two pairs from the set {(1,2),(2,3),(1,3)}{(1,2),(2,3),(1,3)} and form an equivalence relation because such a relation would violate transitivity. For example, if we pick only (1,2)(1,2) and (1,3)(1,3) , then by symmetry we must also have (3,1)(3,1) in the relation. Now by transitivity (3,2)(3,2) must be there, and hence (2,3)(2,3) should be there by symmetry.

Therefore, we have 5 equivalence relations on the set {1,2,3}{1,2,3} . Out of those there are only two of them that contains (1,2)(1,2) and (2,1)(2,1) .

1. {(1,1),(2,2),(3,3),(1,2),(2,1)}{(1,1),(2,2),(3,3),(1,2),(2,1)}
2. {(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)}