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.)
Best Answer
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?
I hope this isn't too confusing. If you have further questions, just leave a comment below.