1. ## Proof regarding functions

Prove by induction that if set A has n elements and set B has m elements, then there are $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.

2. Originally Posted by h2osprey
Prove by induction that if set A has n elements and set B has m elements, then there are $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 $m$ and do the induction over $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 $A = A' \cup \{x \},$ where $A'$ is a set with n elements. a map from A to B can send $x$ to

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

ways to map A to B.