the number of relations on X

Question

Let $X := \{ 1, 2, 3 \}$ . Find the number of relations on $X$.

Solution: $2^{3^2} = 2^9 = 512$.

Could someone explain why is the formula $2^{n^2}$ where $n=|X|$?

Answer 1

A relation on the set is some subset of the Cartesian square of the set. $$R\subseteq X{\times}X $$

You want to count all the possible such subsets.

That is, the size of the Power Set of the Cartesian Square of $X$.

Recall that $\lvert \mathcal P(Z)\rvert = 2^{\lvert Z\rvert}$ .

So if there are $n$ elements in $X$, there are $n^2$ in $X{\times}X$, and there are $2^{n^2}$ elements in the power set $\mathcal P(X{\times}X)$.

That is all.

---

$$\begin{align}\lvert\mathcal P(X{\times}X)\rvert ~=~& 2^{\lvert X\times X\rvert} \\ ~=~& 2^{\lvert X\rvert^2} \\ ~=~& 2^{n^2} \end{align}$$