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.