Question

Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equvalence relation on S are

• A. n and n
• B. $n^2$ and n
• C. $n^2$ and 0
• D. n and 1

Answer 1

The correct option is B $n^2$ and n

Let S he a set of n elements say {1, 2, 3 n}. Now the smallest equivalency relation on S must contain all the reflexive elements {(l, 1). (2. 2), (3.3) (n. n)}: and its cardinality is therefore n. The largest equivalence relation on S is S $\times$ S. which has cardinality of n $\times$ n = $n^2$.
$\therefore$The largest and smallest equivalence relations on S have cardinalities of $n^2$ and n respectively. Correct choice is (b).