How many equivalence relation can be defined on a set of $5$?

Question

The question is how many equivalence relation can be defined on a set of $5$?

I think this is asking how many different ways can we partition a set of $5$, right?

So the answer is

$1$ way: $$\{1\},\{2\},\{3\},\{4\},\{5\}$$

$_5C_2$ ways: $$\{1,2\},\{3\},\{4\},\{5\}$$

$_5C_2\times _3C_2$ ways: $$\{1,2\},\{3,4\},\{5\}$$

$_5C_3$ ways: $$\{1,2,3\},\{4\},\{5\}$$

$_5C_3$ ways: $$\{1,2,3\},\{4,5\}$$

$_5C_4$ ways: $$\{1,2,3,4\},\{5\}$$

$1$ way: $$\{1,2,3,4,5\}$$

So the total number is $1+10+30+10+10+5+1=67$.

Is that correct?

Answer 1

You've made a calculation error, you have double-counted the partitions of type $\{a,b\},\{c,d\},\{e\}$, since $\{a,b\},\{c,d\},\{e\}$ is the same partition as $\{c,d\},\{a,b\},\{e\}$. There are only $15$ of those, not $30$. The correct number of partitions (therefore also the correct number of equivalence classes) is $52$, the $5$th Bell number.

Answer 2

This answer is incorrect with the correct answer of 52. You must have double counted things though I'm not going through to check what. This problem is computing the 5th bell number. For more info http://mathworld.wolfram.com/BellNumber.html.

Otherwise your method is correct.

Answer 3

Yes,since each equivalent relation on a set yields a partition of that set in disjoint equivalence classes, for a finite set, the number of equivalence relations is the number of partitions, i.e. the n-th Bell number for a set of size n. Your calculation, however, is not correct: if $B_{n}$ is the number of partitions on a set of size n, notice $B_{n+1}=\sum_{k=0}^{n}C_{n}^{k}B_{k}$, and $B_{0}=1$. It is then easy to check that $B_{5}=52$

Answer 4

Number of equivalence relation on a set is equal to number of partition of that set containing n elements So number of partition of a set contains 5 elements is 52 ,hence it is total number of equivalence relation on this set ..