How many equivalence relations on a set with 4 elements.

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.

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