# Maximum number of relations?

The question is that we have to prove that if $A$ has $m$ elements and $B$ has $n$ elements, then there are $2^{mn}$ different relations from A to B.

Now I know that a relation $R$ from $A$ to $B$ is a subset of $A \times B$. And as the maximum number of subsets (Elements in the powerset) is $2^{mn}$ so the answer is also the same.

But I don’t get how would I prove this. Should I prove that there are $2^{mn}$ in a powerset and give the definition of a relation and hence conclude that the answer is $2^{mn}$. (If this is the case can you help me with it.)

#### Solutions Collecting From Web of "Maximum number of relations?"

You should prove two statements:

1) If $A$ has $m$ elements and $B$ has $n$ elements, then $A \times B$ has $mn$ elements.

2) If $C$ is a set of $k$ elements, then the power set $P(C)$ has $2^k$ elements.

Regarding 2): Let $C = \{c_1,\ldots,c_k\}$ and consider the mapping
$$f : P(C) \to \{ (a_1,\ldots, a_k) ~ | ~ a_i \in \{0,1\}\}$$
defined in the following way: For $D\subseteq C$ let $f(D) := (d_1,\ldots, d_k)$ where $d_i = 1$ if $c_i \in D$ and $d_i =0$ if $c_i \notin D$. For example $f(\emptyset) = (0,\ldots, 0)$, $f(\{c_2\}) = (0,1,0,\ldots, 0)$ and so on.

This way we associate every subset $D$ of $C$ with a $k$-tuple that has a $1$ at the $i$-th position, if $c_i$ is in $D$ and a $0$ otherwise.

Now one can see that $f$ is a bijection: If $f(D) = f(D’)$, then $D = D’$ and for every sequence $(a_1,\ldots, a_k)$ consisting of $0$’s and $1$’s we can find a matching subset $D \subseteq C$ such that $f(D) = (a_1,\ldots, a_n)$. That $f$ is a bijection means that $P(C)$ and the set of all possible $k$-tuples containing only $0$’s and $1$’s have the same cardinality (number of elements).

Another hint to finish the proof of 2):
$$\{ (a_1,\ldots, a_k) ~ | ~ a_i \in \{0,1\}\} = \underbrace{\{0,1\} \times \ldots \times \{0,1\}}_{k \text{ times}}$$
Can you use 1) now?

$R\subset A\times B$.
Let $A=\{a_1,a_2,…,a_m\}$ and $B=\{b_1,b_2,…,b_n\}$. Recall that $A\times B=\{(a_i,b_j):1\leq i\leq m, 1\leq j\leq n\}$ so $|A\times B|=mn$. Also we have $|2^{A\times B}|=2^{mn}$ Since $R\in 2^{A\times B}$ then there are $2^{mn}$ relations.