ThmDex – An index of mathematical definitions, results, and conjectures.
Number of N-ary relations on a finite set
Formulation 0
Let $X$ be a D17: Finite set such that
(i) $K : = |X| \in \mathbb{N} = \{ 0, 1, 2, 3, \ldots \}$
(ii) $X^N = \prod_{n = 1}^N X$ is a D326: Cartesian product
(iii) $\mathcal{R} : = \{ R : R \subseteq X^N \}$ is a D5494: Set of N-ary relations on $X^N$
Then \begin{equation} |\mathcal{R}| = 2^{K^N} \end{equation}
Formulation 1
Let $X$ be a D17: Finite set such that
(i) $K : = |X| \in \mathbb{N} = \{ 0, 1, 2, 3, \ldots \}$
(ii) $X^N = \prod_{n = 1}^N X$ is a D326: Cartesian product
(iii) $\mathcal{R} : = \{ R : R \subseteq X^N \}$ is a D5494: Set of N-ary relations on $X^N$
Then \begin{equation} |\mathcal{R}| = 2^{\underbrace{K K \cdots K}_{N \text{ times}}} \end{equation}
Proofs
Proof 0
Let $X$ be a D17: Finite set such that
(i) $K : = |X| \in \mathbb{N} = \{ 0, 1, 2, 3, \ldots \}$
(ii) $X^N = \prod_{n = 1}^N X$ is a D326: Cartesian product
(iii) $\mathcal{R} : = \{ R : R \subseteq X^N \}$ is a D5494: Set of N-ary relations on $X^N$
This result is a particular case of R4309: Number of N-ary relations on a finite cartesian product. $\square$