How many equivalence relations on a set with 4 elements.

Question

Let S be a set containing 4 elements (I choose {$a,b,c,d$}). How many possible equivalence relations are there?

So I started by making a list of the possible relations: {$(a,a)(a,b)(a,c)(a,d)(b,a)(b,b). . .(d,d)$}

{$(a,a)(a,b)(a,c). . . . . . . . . . (d,c)$}

{$(a,a)(a,b)(a,c). . . . . . . . . . (d,b)$} etc.

$\vdots$

{}

Then I looked at the first set of relations: $aRa, aRb,$ etc. then I tried to compare relations to see if they are equivalence relations. This is where I got stuck. I realized that there were way too many relations to go through, (without spending all week) and that I didn't want to have to look at each one separately. Is there a better way to do this or am I on the right track?

Answer 1

An equivalence relation divides the underlying set into equivalence classes. The equivalence classes determine the relation, and the relation determines the equivalence classes. It will probably be easier to count in how many ways we can divide our set into equivalence classes.

We can do it by cases:

(1) Everybody is in the same equivalence class.

(2) Everybody is lonely, her class consists only of herself.

(3) There is a triplet, and a lonely person ($4$ cases).

(4) Two pairs of buddies (you can count the cases).

(5) Two buddies and two lonely people (again, count the cases).

There is a way of counting that is far more efficient for larger underlying sets, but for $4$, the way we have described is reasonably quick.

Answer 2

It is equivalent to asking in how many ways can you partition the set! The answer is just the 4th Bell number: $$B_4=15$$
Calulated pretty easily from the case of a $0,1,2,3$ element sets (Which you can solve in your head to be $1,1,2,5$) using the recurrence relation: $$B_4 = \sum_{k=0}^3 \binom{3}{k} B_k = \binom{3}{0} \cdot 1 + \binom{3}{1} \cdot 1 + \binom{3}{2} \cdot 2 + \binom{3}{3} \cdot 5=1 \cdot 1+ 3\cdot 1 + 3 \cdot 2 + 1 \cdot 5 = 15$$ The reasoning behind this recurrence relation is a generalization of what André Nicolas explained.