Why is the number of subsets equal to the number of relations?

Question

In this question I don't understand why the number of subsets is equal to the number of relations.

Any help is welcome.

Answer 1

Firstly, to avoid misunderstandings: the number of relations on A is asserted to be the number of subsets of A x A (and not of A !).

Secondly: this is indicated by the first sentence of the solution: "A relation on A is a subset of A x A" - I hope it is clear that if a relation is a subset (and different subsets are thus different relations), then the number of relations is the number of subsets.

Answer 2

A relation $R$ on a set $A$ is by definition a subset of the set $A \times A$. So to find the numbers of relations on a set $A$, we can simply find the number of subsets $A \times A$.

We know that if $A$ has $n$ elements, then $A \times A$ has $n^2$ elements, and the set of subsets of $A$, also known as the power set $\mathcal{P}(A)$, has $2^n$ elements. Hence, there $2^{n^2}$ subsets of $A \times A$, and this is the same as the number of relations on $A$.