I am just starting to learn about equivalence relations and have a question that I think will help solidify my understanding.

Say you want to define an equivalence relation on set $A$. Is it sufficient to define $S_1, S_2,...,$ and $S_k$ such that $\bigcup\limits_{i=1}^k S_i = A$ and all $S_i$ are pairwise disjoint, setting each $S_i$ to be an equivalence class?

EDIT: I found a proof that there is a one-to-one correspondence between the equivalence relations on a set $A$ and the partitions of $A$, so the answer to the above question is "yes" -- thank you also to the commenters who pointed this out.

Then, I presume, the equivalence relation $p=\bigcup\limits_{i=1}^k (S_i \times S_i)$. Is this correct?

Also, if this is true, then the number of distinct equivalence relations on a set of cardinality $a$ would be $\sum_{i=1}^{a}\frac{a!}{(a-i)!}i^{a-i}$, where $i$ represents the number of equivalence classes (at least 1 and at most $a$). My thinking is that, since you have to put at least 1 element in each group, you can do this in $\frac{a!}{(a-i)!}$ ways. Then, for the rest of the $a-i$ elements, you have $i$ choices. But this is not correct... the correct way of counting equivalence relations is described here (as pointed out in the comments). So where did I go wrong in my counting?

EDIT: the above counting method overcounts by distinguishing by order of groups and order of elements within groups. See the link posted in the comments for the correct solution.

I think the right formula is $\sum_{i=1}^{a}S(a,i)$ where $S$ denotes a Stirling number of the second kind.

  • $\begingroup$ The answer to the question in your 2nd paragraph is "Yes". $\endgroup$ Jun 23, 2019 at 22:49
  • 1
    $\begingroup$ yes, a partition corresponds to an equivalence relation $\endgroup$ Jun 23, 2019 at 22:49
  • 1
    $\begingroup$ See also oeis.org/A000110 $\endgroup$ Jun 23, 2019 at 22:53
  • $\begingroup$ I don't think your counting formula is correct. $\endgroup$
    – Randall
    Jun 23, 2019 at 23:07
  • 1
    $\begingroup$ I see the issue... the ordering within the groups doesn't matter and the ordering of the groups doesn't matter $\endgroup$ Jun 24, 2019 at 0:07


You must log in to answer this question.

Browse other questions tagged .