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