The number of equivalence relations on the set {1, 2, 3} is
A. 5
B. 6
C. 9
D. 4
GATE 1997 · Discrete Mathematics · Relations · medium
Answer: A. 5
- List all partitions of {1, 2, 3}: Partitions of {1,2,3}:
1. {{1,2,3}} — one class (complete relation)
2. {{1,2},{3}} — 1 pairs with 3 alone
3. {{1,3},{2}} — 1 pairs with 2 alone
4. {{2,3},{1}} — 2 pairs with 1 alone
5. {{1},{2},{3}} — discrete (equality only)
Total: 5 partitions.
- Verify using Bell number: The Bell number B(3) = 5 confirms there are 5 partitions and hence 5 equivalence relations on a 3-element set.