Cardinality of Set of Endorelations
Jump to navigation
Jump to search
Theorem
Let $S$ be a finite set.
Let $\card S = n$, where $\card {\, \cdot \,}$ denotes cardinality (that is, the number of elements).
Let $\RR$ denote the set of all endorelations on $S$.
Then the cardinality of $\RR$ is given by:
- $\card \RR = 2^{\paren {n^2} }$
Proof
By definition, an endorelation on $S$ is a relation from $S$ to itself.
From Cardinality of Set of Relations, the number of relations from $S$ to $T$ is equal to $2^{\card S \times \card T}$.
In this case $S = T$ and the result follows.
$\blacksquare$