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}

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$