## Sets of Functions

Consider the set of all functions $f:X\rightarrow \{0,1\}$. Each subset $A\subseteq X$ has such a function, namely its characteristic function, $\chi_A$; moreover, given $f:X\rightarrow\{0,1\}$ we can define the set $A=f^*(\{1\})$ and see that $f=\chi_A$. So the functions $f:X\rightarrow \{0,1\}$ correspond to subsets of $X$.

**Definition.** Given sets $A$, $B$, define \begin{equation*}A^B=\left\{f:B\rightarrow A\right\}\end{equation*} to be the set of all functions from $B$ to $A$.

This notation connects with our powerset notation by writing $2$ for the set $\{0,1\}$ (which has two elements).

**Theorem.** If $A$ has exactly $n$ elements and $B$ has exactly $m$ elements, then $A^B$ has exactly $n^m$ elements.

**Proof.** To define a function $B\rightarrow A$ requires choosing, for each $b\in B$, one of the $n$ elements of $A$.

Each time we make such a choice, there are $n$ options; and we have to make the choice $m$ times. So in total there are $n\cdot n\cdot\cdots \cdot n=n^m$ possibilities. $\Box$