0
$\begingroup$

I am trying to find a formula for number of equivalence relations on a set with n-elements however I am confused.
I have already encountered the idea of "bell's number" and "Stirling numbers of the second kind" however it seems to contradict the meaning of "Relation".
Definition: "Relation" between sets A and B, to be any subset of Cartesian product $A\times B$
Definition: "Equivalence Relation" is a relation that is reflexive, symmetric and transitive.
So, if we suppose that we want to find "equivalence relations" on the set $A=\{a,b,c\}$ we would have the following:
$\{(a,a)\}$
$\{(b,b)\}$
$\{(c,c)\}$
$\{(a,a),(b,b),(c,c)\}$
$\{(a,a),(a,b),(b,a),(b,b)\}$
$\{(a,a),(a,c),(c,a),(c,c)\}$
$\{(b,b),(b,c),(c,b),(c,c)\}$
$\{(a,a),(a,b),(b,a),(b,b),(c,c)\}$
$\{(a,a),(a,c),(c,a),(c,c),(b,b)\}$
$\{(b,b),(b,c),(c,b),(c,c),(a,a)\}$
$\{(b,b),(a,a),(c,c),(b,a),(a,b),(a,c),(c,a),(b,c),(c,b)\}$
which is $11$, however the $B_3=5$ which even if I recursively sum we arrive at $B_1+B_2+B_3=1+2+5=8$.
So, aren't the sets I presented "equivalence relations" on $A$ or the formula I am looking for is different?

$\endgroup$
3
  • 1
    $\begingroup$ Neither $\{(a,a)\}$ nor $\{(b,b)\}$ is an equivalence relation on $A$ because they are not reflexive. $\endgroup$
    – Nothing special
    Commented Mar 9 at 17:55
  • $\begingroup$ Reflexivity means that $xRx$ for any $x$. $\endgroup$
    – Aig
    Commented Mar 9 at 18:00
  • 2
    $\begingroup$ To establish an equivalence relation is the same as to partition a set. So the answer is $B_n$. See the explanations for example here $\endgroup$
    – Aig
    Commented Mar 9 at 18:07

0

Reset to default

You must log in to answer this question.