# Proof regarding functions

• Jan 13th 2009, 08:14 PM
h2osprey
Proof regarding functions
Prove by induction that if set A has n elements and set B has m elements, then there are $\displaystyle m^n$ many functions from A to B.

I see how this is intuitive, but can't figure out how to write a formal proof.
• Jan 13th 2009, 08:42 PM
NonCommAlg
Quote:

Originally Posted by h2osprey
Prove by induction that if set A has n elements and set B has m elements, then there are $\displaystyle m^n$ many functions from A to B.

I see how this is intuitive, but can't figure out how to write a formal proof.

fix $\displaystyle m$ and do the induction over $\displaystyle n.$ if n = 1, then A has only one element and it can be mapped to any of m elements of B. so there are m functions in this case.

now suppose the claim is true for n and let A be a set with n + 1 elements. so $\displaystyle A = A' \cup \{x \},$ where $\displaystyle A'$ is a set with n elements. a map from A to B can send $\displaystyle x$ to

any element of B. so there are $\displaystyle m$ possibilities for the image of $\displaystyle x.$ also by induction hypothesis there are $\displaystyle m^n$ ways to map $\displaystyle A'$ to B. thus there are $\displaystyle m \cdot m^n=m^{n+1}$

ways to map A to B.