ThmDex – An index of mathematical definitions, results, and conjectures.

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$