# How many equivalence relations on a set with 4 elements.

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?

-
Note that an equivalence relation must satisfy $aRa$, $aRb \Rightarrow bRa$ and $aRb, bRc \Rightarrow aRc$ and use this to construct equivalence relations. You'll notice that there are just as many equivalence relations as you can find partitions of your set into disjoint subsets (why?) –  AlexR Feb 14 '14 at 16:42
Did you start with a set containing two elements, then build up to a set containing three elements, then extrapolate? –  abiessu Feb 14 '14 at 16:46
@MJD: Is this really a frequently asked question? –  Asaf Karagila Apr 16 '14 at 5:09
@Asaf I ran into this one in connection with closing this and quickly found these others: 2 3 4 5. I added this post to the common questions list, and the instructions there say to tag such questions with faq. But I'm not sure what the threshold for “frequently asked” is. –  MJD Apr 16 '14 at 13:42

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.

-
Can I simply say that it's the total possible number of partitions which is the power set minus {}? Or 2^n - 1 ? –  Vaibhav Nov 29 '14 at 10:29
That's a numerical coincidence. The pattern is more complicated, (Bell numbers, please see the link in the answer of Dror), with no "closed form" formula. –  André Nicolas Nov 29 '14 at 12:50

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.

-