Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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 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 at 16:46
    
@MJD: Is this really a frequently asked question? –  Asaf Karagila Apr 16 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 at 13:42

2 Answers 2

up vote 9 down vote accepted

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.

share|improve this answer
    
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 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 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.