finding binary relations between two Finite sets? If there are two finite sets $A$ and $B$, then how to achieve the below


*

*How many binary relations between $A$ and $B$?

*How many functions from $A$ to $B$?
$A$ and $B$ should be in terms of cardinality. any suggestions are appreciated.
 A: *

*A binary relation between $A$ and $B$ is just a subset of $A \times B$

*A function from $A$ to $B$ assigns exactly a value in $B$ to each $a \in A$


Counting both in terms of the cardinalities of $A$ and $B$ is left as an exercise.
A: We will prove 2), next we will prove 1) as a consequence of 2).
Let $p = \lvert A\rvert$ and $q = \lvert B\rvert$.
2) Denote $\mathcal{F}(A,B)$ the set of functions from $A$ to $B$.
We prove by induction on $p$ the statement
$$\lvert \mathcal{F}(A,B) \rvert = q^p.$$
If $p = 1$, then $\mathcal{F}(A,B) \to B$, $f\mapsto f(a)$ where $a\in A$ is bijection, so the statement is true.
Now we suppose the statement is true for $n\in\mathbb{N}$ and that $\lvert A \rvert = p + 1$. Let $a\in A$ and $\mathcal{F}_{a,b}(A,B) = \{ f\in\mathcal{F}(A,B) \mid f(a) = b \}$ for all $b\in B$. Clearly,
the family of sets $(\mathcal{F}_{a,b}(A,B))_{b\in A}$ is a partition of $\mathcal{F}(A,B)$, thus
$$
  \lvert \mathcal{F}(A,B) \rvert = \sum_{b\in B} \lvert\mathcal{F}_{a,b}(A,B) \rvert. \qquad (1)
$$
But, for all $b\in B$, we have a bijection
$$
\begin{align*}
  \mathcal{F}_{a,b}(A,B) &\to \mathcal{F}(A \setminus \{a\},B) \\
                     f&\mapsto f_{|A\setminus\{a\}}
\end{align*}
$$
so $\lvert \mathcal{F}_{a,b}(A,B) \rvert = \lvert\mathcal{F}(A\setminus\{a\},B)\rvert$. Moreover $\lvert A\setminus\{a\}\rvert = p$, thus by induction hypothesis $\lvert\mathcal{F}(A,B)\rvert = p^q$. The equation $(1)$ becomes
$$
  \lvert\mathcal{F}(A,B)\rvert = \sum_{b\in B} q^p
  = q \times q^p
  = q^{p + 1}
$$
which proves the statement is true for all $p\in\mathbb{N}$.
1) A binary relation between $A$ and $B$ is a subset of $A\times B$.
So we need to find the cardinal of $\mathcal{P}(A\times B)$.
We have the following bijection:
$$
\begin{align*}
  \mathcal{P}(A\times B) &\to \mathcal{F}(A\times B,\{0,1\}) \\
                  E &\to \chi_E
\end{align*}
$$
where $\chi_E$ is the function defined by
$$
\chi_E(x) =
  \begin{cases}
    1 &\text{if $x\in E$} \\
    0 &\text{if $x\notin E$}.
  \end{cases}
$$
Given that $\lvert A\times B\rvert = pq$ (product rule), 
we use the result of question 2) to conclude that
$$
  \rvert \mathcal{P}(A\times B) \lvert = 2^{pq}.
$$
