How many equivalence relations on a set with 5 elements?
Answers
An equivalence relation is Reflexive, Symmetric and Transitive. Before counting the number of possible equivalence relations on a set |A|=n, let us see an example of a equivalence relation and identify Equivalence Classes in it.
Let A = {1, 2, 3, 4} be a set and R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (3, 4), (4, 3), (4, 4)} be an equivalence relation on A. we see here that the total relation T = {(1, 1), (1, 2), (1, 3), (1, 4)} over the set C1 = {1, 2} which is the subset of A is present in R, i.e subset of R. And also there is no such total relation T’>=T over set C1’>=C1 which is present in R i.e subset of R. Hence we found an equivalence class E1 = {1, 2} over relation R.
Similarly there is another equivalence class E2 = {3, 4} over R. And no more such equivalence classes are present in R. Notice here that E1 and E2 are disjoint sets and this is always true because {E1, E2} i.e {{1, 2}, {3, 4}} is one of the possible partition of the set A.
Hence above equivalence relation R corresponds to the partition {{1, 2}, {3, 4}} of the set A. Similary each and every equivalence relation on A corresponds to one of the partition of A. In fact this mapping is Bijective.
Now we come to our question of finding number of possible equivalence relations on a finite set which is equal to the number of partitions of A. The Bell Numbers count the same. Starting with B0 = B1 = 1, the first few Bell numbers are: