ThmDex – An index of mathematical definitions, results, and conjectures.
Result R4049 on D5348: Set of binary relations
Subresult of R4048: Number of binary relations on binary cartesian product
Number of binary relations on a finite set
Formulation 0
Let $X$ be a D17: Finite set such that
(i) $N : = |X| \in \mathbb{N} = \{ 0, 1, 2, 3, \ldots \}$
(ii) $X \times X$ is the D191: Binary cartesian set product of $X$ with itself
(iii) $\mathcal{B} : = \{ R : R \subseteq X \times X \}$ is the D5348: Set of binary relations on $X$
Then \begin{equation} |\mathcal{B}| = 2^{N^2} \end{equation}
Formulation 1
Let $X$ be a D17: Finite set such that
(i) $N : = |X| \in \mathbb{N} = \{ 0, 1, 2, 3, \ldots \}$
(ii) $X \times X$ is the D191: Binary cartesian set product of $X$ with itself
(iii) $\mathcal{B} : = \{ R : R \subseteq X \times X \}$ is the D5348: Set of binary relations on $X$
Then \begin{equation} |\mathcal{B}| = 2^{N N} \end{equation}
Proofs
Proof 0
Let $X$ be a D17: Finite set such that
(i) $N : = |X| \in \mathbb{N} = \{ 0, 1, 2, 3, \ldots \}$
(ii) $X \times X$ is the D191: Binary cartesian set product of $X$ with itself
(iii) $\mathcal{B} : = \{ R : R \subseteq X \times X \}$ is the D5348: Set of binary relations on $X$
This result is a particular case of R4048: Number of binary relations on binary cartesian product. $\square$