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?