Question 25 of 161MediumMCQ
The number of non-empty equivalence relations on the set {1,2,3} is :
Solutions · 1
Official solution
An equivalence relation on a finite set is uniquely determined by its partition into equivalence classes. Hence, counting the number of equivalence relations on a set is equivalent to counting the number of ways to partition that set.
Step: Counting partitions of {1,2,3}
We want all possible ways to split the set {1,2,3} into nonempty subsets (its ``blocks'').
3 blocks (each element in its own block)
{{1},{2},{3}}.
2 blocks
{{1,2},{3}}
{{1,3},{2}}
{{2,3},{1}}
1 block (all elements together)
{{1,2,3}}.
Counting these, there are a total of 5 distinct partitions, and thus 5 equivalence relations on the set {1,2,3}.
All equivalence relations are automatically nonempty (they include at least (1,1),(2,2),(3,3) because they are reflexive), so the answer to ``the number of nonempty equivalence relations'' is also 5.
Answer: Option C (5)
Answer the question to unlock