Prove by induction that if set A has n elements and set B has m elements, then there are many functions from A to B.

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

Printable View

- Jan 13th 2009, 09:14 PMh2ospreyProof regarding functions
Prove by induction that if set A has n elements and set B has m elements, then there are 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, 09:42 PMNonCommAlg
fix and do the induction over 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 where is a set with n elements. a map from A to B can send to

any element of B. so there are possibilities for the image of also by induction hypothesis there are ways to map to B. thus there are

ways to map A to B.