An equivalence relation on a finite set is uniquely determined by its partition into equivalence classes. Hence, counting the number of equivalence relations on a set is equivalent to counting the number of ways to partition that set.

Step: Counting partitions of $\{1,2,3\}$

We want all possible ways to split the set $\{1,2,3\}$ into nonempty subsets (its “blocks”).

3 blocks (each element in its own block)

$ \{\{1\}, \{2\}, \{3\}\}. $

2 blocks

$\{\{1,2\}, \{3\}\}$

$\{\{1,3\}, \{2\}\}$

$\{\{2,3\}, \{1\}\}$

1 block (all elements together)

$ \{\{1,2,3\}\}. $

Counting these, there are a total of 5 distinct partitions, and thus 5 equivalence relations on the set $\{1,2,3\}$.

All equivalence relations are automatically nonempty (they include at least $(1,1), (2,2), (3,3)$ because they are reflexive), so the answer to “the number of nonempty equivalence relations” is also 5.

Answer: Option C (5)