Project ForgeDiscrete Mathematics
Set Theory & Abstract Algebra
GATE 2007
Medium
Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equivalence relations on S are
- An and n
- n² and n
- Cn² and 0
- Dn and 1
Explanation
The largest equivalence relation on S is the universal relation (every element related to every element, including itself), giving n×n = n² ordered pairs. The smallest is the identity relation (every element related only to itself), giving exactly n ordered pairs.
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.