Question

Determine the number of different equivalence relations on a set with three elements by listing them.

Short answer

There are \(5\) distinct equivalence relations on \(S\), as listed in (1) to (4) below.

Step-by-step solution

Given data

Let the three element set \(S = \{ a,b,c\} \).

Concept  used of Equivalence relation

An equivalence relation is a binary relation that is reflexive, symmetric and transitive.

Find the equivalence class

Any equivalence relation on \(S\) necessarily contains the pairs \((a,a),(b,b)and(c,c)(\) In view of reflexivity). The smallest such equivalence relation is

\(\{ (a,a),(b,b),(c,c)\} \) …..(1)

Assume it contains \((a,b)\) but not \((b,c)\). Symmetry implies it contains \((b,a)\) as well, but not \((c,b)\).

Such a relation is completely specified as

\(\{ (a,a),(b,b),(c,c),(a,b),(b,a)\} \) …..(2)

Similarly we have the equivalence relations

\(\begin{array}{l}\{ (a,a),(b,b),(c,c),(b,c),(c,b)\} \\\{ (a,a),(b,b),(c,c),(a,c),(c,a)\} \end{array}\) …..(3)

And finally, the entire set of ordered pairs \(\{ (a,a),(b,b),(c,c),(a,b),(b,a),(a,c),(c,a),(b,c),(c,b)\} \) ……(4)

The list (1) to (4) is the \(5\) distinct equivalence relations on the three element set \(S\).