Set Induction

1. Oct 14, 2007

SahDu

Hey guys. I need some help solving this proof using induction:

Prove that for all non-empty finite sets A and B, there are |B|^|A| functions from A to B

(where |B| and |A| obviously represents the cardinality of B and A respectively.)

Thanks in advance for the help, since I am pretty stuck. Thanks again!

Jeff

EDIT: Sorry, to reiterate...these are the practice problems we were told to look at before the test...so it's not HW.

Last edited: Oct 14, 2007
2. Oct 15, 2007

ZioX

But you still have to demonstrate that you've tried solving this problem!

3. Oct 15, 2007

SahDu

Oh haha! Sorry. Here is what I got and then got stuck:

b. Proof: For all non-empty finite sets A and B, there are |B||A| functions from A to B.
Assume for all non empty finite sets, for any proper subset Z C A and Y C B, we have |Y||Z| functions from Z to Y
Let z be an arbitrary element of A, let y be an arbitrary element of B, let Z=A\{z} and let Y=B\{y}
Therefore, we have functions from Z to {y}, Z to Y, {z} to {y} and {z} to Y

I thought I could use induction to say it = 1+|Y|^|Z|+1+|Y|...but I couldn't get that to boil down to |B|^|A|

Jeff

4. Oct 15, 2007

zhentil

Look at it non-rigorously. For each element of A, there are |B| places to send it. That's |B|^|A| functions.