finding binary relations between two Finite sets?

Question

If there are two finite sets $A$ and $B$, then how to achieve the below

1. How many binary relations between $A$ and $B$?

2. How many functions from $A$ to $B$?

$A$ and $B$ should be in terms of cardinality. any suggestions are appreciated.

Answer 1

1. A binary relation between $A$ and $B$ is just a subset of $A \times B$
2. 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.

Answer 2

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}. $$