1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Set Induction

  1. Oct 14, 2007 #1
    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. jcsd
  3. Oct 15, 2007 #2
    But you still have to demonstrate that you've tried solving this problem!
     
  4. Oct 15, 2007 #3
    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
     
  5. Oct 15, 2007 #4
    Look at it non-rigorously. For each element of A, there are |B| places to send it. That's |B|^|A| functions.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?