Let S be a set of n elements. The number of ordered pairs in the largest and…
2007
Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equivalence relations on S are:
- A.
n and n
- B.
n2 and n
- C.
n2 and 0
- D.
n and 1
Attempted by 306 students.
Show answer & explanation
Correct answer: B
Answer: The largest equivalence relation has n^2 ordered pairs and the smallest has n ordered pairs.
Why the largest is n^2: The universal relation S×S contains every ordered pair (a,b) with a,b in S. Since |S| = n, the total number of ordered pairs is n × n = n^2.
Why the smallest is n: The identity relation {(x,x) : x in S} is an equivalence relation and contains exactly the n reflexive pairs. Reflexivity is required for any equivalence relation, so no equivalence relation can have fewer than these n pairs; hence the identity relation is the smallest and has n ordered pairs.
Largest equivalence relation: S×S → n^2 ordered pairs
Smallest equivalence relation: identity relation {(x,x)} → n ordered pairs
A video solution is available for this question — log in and enroll to watch it.