### 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.

### License

BSD License

### Topics

- Mathematics/Combinatorics

### Session Card_Equiv_Relations

- Card_Equiv_Relations
- Card_Partial_Equiv_Relations

### Depends on

- Spivey’s Generalized Recurrence for Bell Numbers

### Used by

- Enumeration of Equivalence Relations

### Auto-related entries

- From Abstract to Concrete Gödel’s Incompleteness Theorems—Part I
- From Abstract to Concrete Gödel’s Incompleteness Theorems—Part II
- Cardinality of Multisets

## Cite

×

Card_Equiv_Relations-AFP

    @article{Card_Equiv_Relations-AFP,
      author  = {Lukas Bulwahn},
      title   = {Cardinality of Equivalence Relations},
      journal = {Archive of Formal Proofs},
      month   = {May},
      year    = {2016},
      note    = {\url{https://isa-afp.org/entries/Card_Equiv_Relations.html},
                 Formal proof development},
      ISSN    = {2150-914x},
    }

Download

## Download

× Download latest

Older releases:

- Sep 13, 2023 : Isabelle2023
- Oct 27, 2022 : Isabelle2022
- Dec 14, 2021 : Isabelle2021-1
- Feb 23, 2021 : Isabelle2021
- Apr 18, 2020 : Isabelle2020
- Jun 11, 2019 : Isabelle2019
- Aug 16, 2018 : Isabelle2018
- Oct 10, 2017 : Isabelle2017
- Dec 17, 2016 : Isabelle2016-1
- May 24, 2016 : Isabelle2016