in Set Theory & Algebra
496 views
0 votes
0 votes
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?
in Set Theory & Algebra
by
496 views

1 Answer

3 votes
3 votes
Best answer

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

selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true