Question

Equivalent Relations..

a-) Determine the number of different equivalence relations on a set with 4 elements.

b-) Generalize your answer to part (a) for a set with n elements.

Answer 1

a)No of equivalence classes with 4 elements is

There are five integer partitions of 4: 4, 3+1, 2+2, 2+1+1, 1+1+1+1. So we just need to calculate the number of ways of placing the four elements of our set into these sized bins.

4
There is just one way to put four elements into a bin of size 4. This represents the situation where there is just one equivalence class (containing everything), so that the equivalence relation is the total relationship: everything is related to everything.
3+1
There are four ways to assign the four elements into one bin of size 3 and one of size 1. The corresponding equivalence relationships are those where one element is related only to itself, and the others are all related to each other. There are clearly 4 ways to choose that distinguished element.
2+2
There are (42)/2=6/2=3(42)/2=6/2=3 ways. The equivalence relations we are looking at here are those where two of the elements are related to each other, and the other two are related to themselves. So, start by picking an element, say 1. Then there are three things that 1 could be related to. Once that element has been chosen, the equivalence relation is completely determined.
2+1+1
There are (42)=6(42)=6 ways.
1+1+1+1
Just one way. This is the identity equivalence relationship.
Thus, there are, in total 1+4+3+6+1=15 partitions on {1, 2, 3, 4}{1, 2, 3, 4}, and thus 15 equivalence relations.

b) For n elements the no of equivalence classes is given by Bell Numbers

The nth of these numbers, B_n, counts the number of different ways to partition a set that has exactly n elements, or equivalently, the number of equivalence relations on it