A partial equivalence relation is a relation that is symmetric and transitive. The number of equivalence relations on a set is given by the Bell numbers. How can I count the partial equivalence relations on a set $\{ 1, \cdots , n\} $?
$\begingroup$ $\endgroup$
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
If $x\sim y$, then by symmetry $y\sim x$ so by transitivity $x\sim x$. Thus an element related to any other element is also related to itself. The set therefore decomposes into two subsets; on one the partial equivalence relation is empty and on the other it is an equivalence relation. Thus the partial equivalence relations on $[n]$ are in bijection with the equivalence relations on $[n+1]$: Just remove the equivalence class containing $n+1$. So the number of partial equivalence relations on $[n]$ is the Bell number $B_{n+1}$.
