Exercise 6.7

Proof. As is customary, denote the set of all functions from $A$ to $B$ by $B^A$. First, if $A=\varnothing$, then the only function from $A$ to $B$ is the vacuous function $\text{∅}$ so that $B^A=\left\{\text{∅}\right\}$, which is clearly finite. So assume that $A\ne \varnothing$. Then, since $A$ is finite, there is a bijection $f$ from $A$ to $\left\{1,\dots ,n\right\}$ for some $n\in {\mathbb{Z}}_{\text{+}}$, noting that of course $f^{-1}$ is then a bijection from $\left\{1,\dots ,n\right\}$ to $A$.

We construct a bijection $h$ from $B^A$ to $B^n$. So, for any $g\in B^A$ set $h(g)=g\circ f^{-1}$, noting that clearly this is a function from $\left\{1,\dots ,n\right\}$ to $B$. Hence $h$ is a function from $B^A$ to $B^n$.

To show that $h$ is injective consider $g$ and $g^{\prime }$ in $B^A$ where $g\ne g^{\prime }$. It then follows that there is an $a\in A$ where $g(a)\ne g^{\prime }(a)$. Then let $k=f(a)$ so that clearly $f^{-1}(k)=a$ and $k\in \left\{1,\dots ,n\right\}$. We then have that $(g\circ f^{-1})(k)=g(f^{-1}(k))=g(a)\ne g^{\prime }(a)=g^{\prime }(f^{-1}(k))=(g^{\prime }\circ f^{-1})(k)$ so that it must be that $h(g)=g\circ f^{-1}\ne g^{\prime }\circ f^{-1}=h(g^{\prime })$. Since $g$ and $g^{\prime }$ were arbitrary, this shows that $h$ is injective.

Now consider any function $i\in B^n$ and let $g=i\circ f$ so that clearly $g$ is a function from $A$ to $B$ since $f:A\to \left\{1,\dots ,n\right\}$ and $i:\left\{1,\dots ,n\right\}\to B$. Hence $g\in B^A$, and $h(g)=g\circ f^{-1}=(i\circ f)\circ f^{-1}=i\circ (f\circ f^{-1})=i$. Since $i$ was arbitrary, this shows that $h$ is surjective as well.

Hence $h$ is bijection from $B^A$ to $B^n$. Now, since $B^n$ is a finite cartesian product of finite sets (since $B$ is finite), it is finite by Corollary 6.8. Thus it must be that $B^A$ is also finite since there is a bijection between them. □