# Thread: Proof by induction: For finite sets A, B w/ cardinality n, m >= 1, show there are...

1. ## Proof by induction: For finite sets A, B w/ cardinality n, m >= 1, show there are...

Let A and B be finite sets of cardinality n and m respectively, where n and m are positive natural numbers.

Show, using induction on n, that there are mn functions from A to B.

Would i be ok to use base step as n = 1? for a function A -> B for one in A

A (x) mapping to B (a1,a2,a3.... am)

The number of functions possible for n-1 is m^n

I don't know how to go on with the induction step. Any ideas?

2. Originally Posted by sita
Let A and B be finite sets of cardinality n and m respectively, where n and m are positive natural numbers.

Show, using induction on n, that there are mn functions from A to B.

Would i be ok to use base step as n = 1? for a function A -> B for one in A

A (x) mapping to B (a1,a2,a3.... am)

The number of functions possible for n-1 is m^n

I don't know how to go on with the induction step. Any ideas?
Hi sita,

A couple of remarks about you thoughts:
• Yes, it is OK to take $n = 1$ as the base case. The base case should be the smallest possible case covered by the hypothesis. In this case, the hypothesis says that $n > 0$.
• Concerning the induction step, if $A$ contains $n-1$ elements, the number of functions would be $m^{n-1}$ by the induction hypothesis, not $m^n$ as you wrote.

This being said, the idea would be to assume that $A$ contains n elements, and to write $A = A'\cup\{a_n\}$, where $A'$ contains $n-1$ elements.

To define a function $f : A\to B$, you must define $f(x)$ for all $x\in A'$, and for $x = a_n$ (i. e., you must define $f(a_n)$).

This means that a function $f : A\to B$ is defined by:

• a function $f': A'\to B$, and the induction hypothesis tells you how many such functions exist.
• for each such function, the image $f(a_n)\in B$, and there are $m$ possible choices for this.

Can you put the pieces together ?

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•