For all finite sets $A$ and $B$, $\{ f:B\to A \}$ is finite and its (finite) cardinality is $|A|^{|B|}$.

Question

In Halmos' Naive Set Theory (towards the end of the "Arithmetic" chapter) he mentions the titular claim:

For all finite sets $A$ and $B$, $\{ f:B\to A \}$ is finite and its (finite) cardinal is $|A|^{|B|}$ where $|A|$ and $|B|$ are the (finite) cardinals of $A$ and $B$, respectively.

Halmos does not provide a hint for this proof. Can the Math StackExchange community provide a hint?

*Let it be known that I intuitively accept the claim, but the proof I find difficult. The proof boils down to constructing a bijection between $\{f:B\to A\}$ and $\{n\in\mathbb{N}:n<|A|^{|B|}\}$. I have a feeling it will require a proof by induction.

Answer 1

We use the notation $B^A$ to denote the collection of all maps $A\to B$ (I hope this is plebeian enough for Cameron!).

We will show that $|B^A|=|B|^{|A|}$ by inducting on $|A|$.

The base case $|A|=0$ holds since there is a unique map $\varnothing\to B$. If this seems iffy to you, then you could make the base case $|A|=1$ and convince yourself that there are exactly $|B|$ maps $A\to B$ when $|A|=1$. Either way, the base case holds.

Now, suppose inductively that the claim is true whenever $|A|\leq n$ and assume $|A|=n+1$. Then there exists a $*\in A$ and \begin{align*} |B^A| &\overset{\circ}{=} |B^{A\setminus\{*\}}|\times|B^{\{*\}}| \\ &= |B|^{|A\setminus\{*\}|}\times|B|^{|\{*\}|} \\ &= |B|^{n}\times|B| \\ &= |B|^{n+1} \\ &= |B|^{|A|} \end{align*} The only equality that is not immediately obvious is the one marked with a $\circ$. Can you prove this equality?

Answer 2

The cardinality of the set of functions $A \to B$ is $|B|^{|A|}$, not $|A|^{|B|}$.

The proof of this fact by induction on $|A|$ is reasonably straightforward. This is probably enough of a hint; let me know in the comments if you want more help.

Answer 3

I think the proof is much simpler than what has been indicated. These are finite sets. How many ways can you form a function $f:A\rightarrow B$? There are $|A|$ elements $a_1,a_2,\ldots,a_{|A|}$ of $A$. For the first element, there are $|B|$ possible values to choose for $f(a_1)$. For each of these, there are $|B|$ possible values to choose for $f(a_2)$. Continuing for each of the $|A|$ elements of $A$, we see that there are altogether $$\underbrace{|B|\cdot|B|\cdot\ldots\cdot|B|}_{|A|\textrm{ factors}}=|B|^{|A |}$$ distinct functions since each distinct choice of assignments determines a distinct function.