Set Theory

Question

If A = {1,2,3...n}, then number of equivalence relations possible on A , which are also surjection on A is ________________?

How to approach this type of problems?

Answer 1

An equivalence relation is Reflexive, Symmetric and Transitive. Since it is Reflexive, an Equivalence relation on $A$ is Always a surjection on $A$. So, You need not confuse at the "Surjection" part and just think about finding the number of Equivalence relations on set of $n$ elements. 

Furthermore, counting the number of equivalence relations on a large set is Not an easy task as there is No simple direct formula to do so (Though there is a concept/formula named "Bell's numbers" which gives the answer but it is tedious and not worth remembering as long as GATE or any other exams are concerned. Unless you are doing PhD in maths, I'd say no need remembering it or digging into it.)

How to approach this type of problems?

In exams they won't ask you this. They might ask the number of equivalence relations on sets of small cardinality like 3,4,5 etc... In which case you can do it manually by finding the number of possible partitions of that set. There's a bijection between equivalence relations on $A$ and the number of partitions on that set. 

https://www.geeksforgeeks.org/number-possible-equivalence-relations-finite-set/

https://math.stackexchange.com/questions/703475/determine-the-number-of-equivalence-relations-on-the-set-1-2-3-4