ThmDex – An index of mathematical definitions, results, and conjectures.
Number of N-ary relations on a finite cartesian product
Formulation 0
Let $X_1, \ldots, X_N$ each be a D17: Finite set such that
(i) $K_1, \ldots, K_N \in \mathbb{N}$ are each a D996: Natural number
(ii) \begin{equation} |X_1| = K_1, \quad \ldots, \quad |X_N| = K_N \end{equation}
(iii) $X : = \prod_{n = 1}^N X_n$ is the D326: Cartesian product of $X_1, \dots, X_N$
(iv) $\mathcal{R} : = \{ R : R \subseteq X \}$ is a D5494: Set of N-ary relations on $X$
Then \begin{equation} |\mathcal{R}| = 2^{\prod_{n = 1}^N K_n} \end{equation}
Formulation 1
Let $X_1, \ldots, X_N$ each be a D17: Finite set such that
(i) $K_1, \ldots, K_N \in \mathbb{N}$ are each a D996: Natural number
(ii) \begin{equation} |X_1| = K_1, \quad \ldots, \quad |X_N| = K_N \end{equation}
(iii) $X : = X_1 \times \cdots \times X_N$ is the D326: Cartesian product of $X_1, \dots, X_N$
(iv) $\mathcal{R} : = \{ R : R \subseteq X \}$ is a D5494: Set of N-ary relations on $X$
Then \begin{equation} |\mathcal{R}| = 2^{K_1 K_2 \cdots K_N} \end{equation}
Subresults
R4310: Number of N-ary relations on a finite set
R4048: Number of binary relations on binary cartesian product
Proofs
Proof 0
Let $X_1, \ldots, X_N$ each be a D17: Finite set such that
(i) $K_1, \ldots, K_N \in \mathbb{N}$ are each a D996: Natural number
(ii) \begin{equation} |X_1| = K_1, \quad \ldots, \quad |X_N| = K_N \end{equation}
(iii) $X : = \prod_{n = 1}^N X_n$ is the D326: Cartesian product of $X_1, \dots, X_N$
(iv) $\mathcal{R} : = \{ R : R \subseteq X \}$ is a D5494: Set of N-ary relations on $X$
Since $X_1, \ldots, X_N$ are finite sets, then result R1832: Cardinality of a finite cartesian product of finite sets shows that \begin{equation} |X| = \left| \prod_{n = 1}^N X_n \right| = \prod_{n = 1}^N K_n \end{equation} Notice that $\mathcal{R}$ is the D80: Power set of $X$; this result is therefore now a consequence of R1839: Cardinality of power set of a finite set. $\square$