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

#### sita

##### New member
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?

Last edited by a moderator:

#### barrick

##### New member
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 $$\displaystyle 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 $$\displaystyle n > 0$$.
• Concerning the induction step, if $$\displaystyle A$$ contains $$\displaystyle n-1$$ elements, the number of functions would be $$\displaystyle m^{n-1}$$ by the induction hypothesis, not $$\displaystyle m^n$$ as you wrote.

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

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

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

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

Can you put the pieces together ?

Last edited by a moderator: