Consider the set of all functions . Each subset has such a function, namely its characteristic function, ; moreover, given we can define the set and see that . So the functions correspond to subsets of .
Definition. Given sets , , define
to be the set of all functions from to .
This notation connects with our powerset notation by writing for the set (which has two elements).
Theorem. If has exactly elements and has exactly elements, then has exactly elements.
Proof. To define a function requires choosing, for each , one of the elements of .
Each time we make such a choice, there are options; and we have to make the choice times. So in total there are possibilities.