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

[sita]

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 mⁿ 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?

 

[barrick]

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 mⁿ 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 ?