Cardinality of Equivalence Relations

Title:	Cardinality of Equivalence Relations
Author:	Lukas Bulwahn (lukas /dot/ bulwahn /at/ gmail /dot/ com)
Submission date:	2016-05-24
Abstract:	This entry provides formulae for counting the number of equivalence relations and partial equivalence relations over a finite carrier set with given cardinality. To count the number of equivalence relations, we provide bijections between equivalence relations and set partitions, and then transfer the main results of the two AFP entries, Cardinality of Set Partitions and Spivey's Generalized Recurrence for Bell Numbers, to theorems on equivalence relations. To count the number of partial equivalence relations, we observe that counting partial equivalence relations over a set A is equivalent to counting all equivalence relations over all subsets of the set A. From this observation and the results on equivalence relations, we show that the cardinality of partial equivalence relations over a finite set of cardinality n is equal to the n+1-th Bell number.
BibTeX:	@article{Card_Equiv_Relations-AFP, author = {Lukas Bulwahn}, title = {Cardinality of Equivalence Relations}, journal = {Archive of Formal Proofs}, month = may, year = 2016, note = {\url{http://isa-afp.org/entries/Card_Equiv_Relations.html}, Formal proof development}, ISSN = {2150-914x}, }
License:	BSD License
Depends on:	Bell_Numbers_Spivey
Status: [ok]	This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.