Let \(A = \{1, 2, 3, 4\}\). The number of equivalence relations on A that have exactly two equivalence classes is
Answer & explanation
Correct answer: option 1
The correct answer is Option (1) → 7
An equivalence relation on A is fixed by its equivalence classes, which split A into non-empty parts with no common element. So we count the ways of splitting A into exactly two parts.
The two parts have sizes 3 and 1, or 2 and 2.
Sizes 3 and 1: the single element can be any of the 4 elements:
{1}, {2, 3, 4}
{2}, {1, 3, 4}
{3}, {1, 2, 4}
{4}, {1, 2, 3}
Sizes 2 and 2: the partner of 1 can be 2, 3 or 4, and the other two elements form the second part:
{1, 2}, {3, 4}
{1, 3}, {2, 4}
{1, 4}, {2, 3}
So the number of such equivalence relations is
\(4 + 3 = 7\)