The number of non-empty equivalence relations on the set {1,2,3} is :

Solution

Maths sir · 3 steps

Every equivalence relation is just a way of splitting the set into groups, so count the splits.

1. Relations as groups. An equivalence relation sorts the elements into classes. Elements in the same class are related to each other, and to nothing outside it. So each equivalence relation matches exactly one partition of {1,2,3}, and each partition gives exactly one relation.

   Partition	Relation (pairs besides (1,1),(2,2),(3,3))	Number of pairs
   {1},{2},{3}	none (identity relation)	3
   {1,2},{3}	(1,2),(2,1)	5
   {1,3},{2}	(1,3),(3,1)	5
   {2,3},{1}	(2,3),(3,2)	5
   {1,2,3}	all six off-diagonal pairs (universal relation)	9

2. Check non-empty. Every one of these contains (1,1),(2,2),(3,3), so all are non-empty. The empty relation is not reflexive, so it was never an equivalence relation to begin with.
3. So. There are 5 non-empty equivalence relations on {1,2,3}, option (c).

The idea to keep. Equivalence relations on a set match its partitions one to one. For 3 elements that is the Bell number 5, for 4 elements it is 15.

Answer from the NTA final answer key. Solution by PrepWiser.