Proving Non-Empty Finite Sets with Induction: A Challenge

[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.

 

[ZioX]

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

 

[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

 

[zhentil]

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