The Number of Distinct Relations on a Finite Set

Recall from the Relations on Sets page that if $X$ is a set then a relation $R$ on $X$ is a subset of $X \times X$ where if $(x, y) \in R$ we say that $x \: R \: y$.

Now consider a finite $n$-element set $X = \{ x_1, x_2, ..., x_n \}$. How many possible distinct relations $R$ exist on $X$? The following theorem gives us the answer.

Theorem 1: If $X = \{ x_1, x_2, ..., x_n \}$ is a finite $n$-element set then the number of distinct relations $R$ on $X$ is $\displaystyle{2^{n^2}}$.

• Proof: Let $X = \{ x_1, x_2, ..., x_n \}$ be a finite $n$-element set. Consider the Cartesian product:

(1)

\begin{align} \quad X \times X = \{ (x, y) : x, y \in X \} \end{align}

• Notice that the Cartesian product $X \times X$ contains pairs of elements from $X$. For each pair $(x, y) \in X \times X$ we have that the value of $x$ is one of the $n$ elements in $X$ and that $y$ is one of the $n$ elements in $X$. There are thus $n^2$ possible ordered pairs $(x, y)$ where $x, y \in X$.

• Now let $R \subseteq X \times X$. For each of the $n^2$ ordered pairs $(x, y)$ we have that either $(x, y) \in R$ or $(x, y) \not \in R$. So, for each pair $(x, y)$ we have two choices. Thus the number of distinct relations $R$ on $X$ is $2^{n^2}$. $\blacksquare$

Corollary 1: If $X = \{ x_1, x_2, ..., x_n \}$ is a finite $n$-element set then the number of distinct reflexive relations $R$ on $X$ is $2^{n^2-n}$.

• Proof: Let $X = \{x_1, x_2, ..., x_n \}$ be a finite $n$-element set. Consider the Cartesian product $X \times X$ again. Once again, we note that there are $n^2$ possible ordered pairs $(x, y)$ where $x, y \in X$.

• Let $R \subseteq X \times X$. Since $R$ is reflexive we have that for all $x \in X$ that $x \: R \: x$, i.e., $(x, x) \in R$. Therefore we require that the $n$ ordered pairs $(x_1, x_1), (x_2, x_2), ..., (x_n, x_n) \in R$. Out of the $n^2 - n$ ordered pairs $(x, y) \in X$ left we have that either $(x, y) \in X$ or $(x, y) \not \in X$. So, for each pair $(x, y)$ we have two choices. Thus the number of distinct reflexive relations $R$ on $X$ is $2^{n^2 - n}$. $\blacksquare$