Suppose A is a finite set with n elements. The number of elements in the largest equivalence relation of A is A. n B. n^2 C. 1 D. n+1

GATE 1998 · Discrete Mathematics · Relations · medium

Answer: B. n^2

1. Identify the largest equivalence relation: The coarsest partition of A is {A} itself (one block containing all n elements). The corresponding equivalence relation is A x A — every element is related to every element. This has n * n = n^2 ordered pairs.
2. Verify A x A is an equivalence relation: All three conditions hold for A x A — it is indeed an equivalence relation with n^2 elements.