Question

Suppose R is an equivalence relation on a finite set A, and every equivalence class has the same cardinality m. Express |R| in terms of m and |A|.

Explain why the answer is m|A|

Answer 1

|A| is the number of elements in A.

We know, equivalence classes form partition (mutually disjoint & exhaustive) of a set.

Also, |R| denotes the total number of elements in the equivalence relation R.

Now, each equivalence class (whose representative is some element 'a' of the finite set A) has the same cardinality m.

So, corresponding to each of the elements of A, i.e. corresponding to each of the |A| elements, there are possibly equivalence classes of cardinality m each.

So, we have a total of m.|A| elements in all the possible equivalence classes combined.

So, R is the accumulation of such equivalence classes.

So, |R| = m.|A|