Count number of Equivalence Relations

anirban

New member
Joined
Sep 26, 2008
Messages
4
How to count number of equivalence relation possible on a set? For instance how to find the number of equivalence relations of the set {1,2,3,4} ? Any formula or concept please?
 
Hello, anirban!

I don't understand the question,
but I will take a guess at what is expected here . . .


How to count number of equivalence relations possible on a set?
For instance, how to find the number of equivalence relations of the set {1,2,3,4} ?
Any formula or concept please?

A relation is a connection between two elements of a set (not necessarily distinct).

It has the form: .xRy\displaystyle x R y, where x\displaystyle x and y\displaystyle y are elements of the set.

Hence, the question could be "How many different ordered pairs of elements can be made?"


In this example, there are 4 choices for the first element and 4 for the second.
. . Hence, there are: .42=16\displaystyle 4^2 \,=\,16 possible pairs.

They are:   {1R11R21R31R42R12R22R32R43R13R23R33R44R14R24R34R4}\displaystyle \text{They are: }\;\begin{Bmatrix}1R1 & 1 R 2 & 1 R 3 & 1R4 \\ 2R1 & 2R2 & 2R3 & 2R4 \\ 3R1 & 3R2 & 3R3 & 3R4 \\ 4R1 &4R2 & 4R3 & 4R4 \end{Bmatrix}


How many of these are "equivalence relations"? . . . Who knows?

 
Thanks but just now got the answer. This can be evaluated using Bells triangle! :)
 
Top