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.



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?

  • 2
    $\begingroup$ 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?) $\endgroup$
    – AlexR
    Feb 14, 2014 at 16:42
  • 1
    $\begingroup$ Did you start with a set containing two elements, then build up to a set containing three elements, then extrapolate? $\endgroup$
    – abiessu
    Feb 14, 2014 at 16:46
  • $\begingroup$ @MJD: Is this really a frequently asked question? $\endgroup$
    – Asaf Karagila
    Apr 16, 2014 at 5:09
  • $\begingroup$ @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. $\endgroup$
    – MJD
    Apr 16, 2014 at 13:42

3 Answers 3


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.

  • $\begingroup$ Can I simply say that it's the total possible number of partitions which is the power set minus {}? Or 2^n - 1 ? $\endgroup$
    – Vaibhav
    Nov 29, 2014 at 10:29
  • 3
    $\begingroup$ 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. $\endgroup$ Nov 29, 2014 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.


Ways of selecting any of the following elements out of 4 : (i) 1 element : C(4,1) (ii) 2 elements : C(4,2) (iii) 3 elements : C(4,3) (iv) 4 elements : C(4,4)

Total partitions = C(4,1) + C(4,2) + C(4,3) + C(4,4) = 15


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .