Sets of Functions – Foundations of Mathematics

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$