Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: How to explain?

  1. Jan 11, 2010 #1
    1. The problem statement, all variables and given/known data

    (1)If C is a set with c elements , how many elements are in the power set of C ? explain your answer.
    (2)If A has a elements and B has b elements , how many elements are in A x B ? explain your answer.

    2. Relevant equations



    3. The attempt at a solution

    (1)The answer is 2 to the power of c / 2^c ..~ but how am i going to explain ?
    (2)The answer is a*b elements . but still don't even know how to explain ..~

    sorry for the stupid question ..~ but i really curious want to know how to explain it ..~
     
  2. jcsd
  3. Jan 11, 2010 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    The second one is straightforward counting.
    How many combinations are there, with one element from A and one element from B? It's like asking: if I have 10 boys and 8 girls, how many combinations of a boy and a girl are there? Well, for each boy I pick there are 8.

    For the first one, there is an argument which I find rather nice myself. An element from the power set is a subset of C. So suppose that we can order the element of C in some way (we have a bijection to (a subset of) natural numbers, which we can use). Now I can encode a subset of C, by writing down a 0 or 1 in the nth place, depending on whether the nth element of C is in my subset. So for example, if C = {1, 2, 3, 4, 5} then I would encode {1, 3, 5} by 10101, {1, 2} by 11000 and {1, 4, 5} by 10011. You can check that this encodes every subset of C uniquely, and that every combination of c zeroes and ones encodes a subset (even 00....0). Now all you have to do is read this as a binary number in c bits, how many of these are there?
     
  4. Jan 11, 2010 #3
    o..~ nice explaination ..~ so the nth element is 11111 ..? from 00000 to 11111 ??
    can u explain about this line ?
    You can check that this encodes every subset of C uniquely, and that every combination of c zeroes and ones encodes a subset (even 00....0)...
    Im not quite sure what it is trying to convey ?
     
  5. Jan 11, 2010 #4

    Mark44

    Staff: Mentor

    What Compuchip is saying for his example is that every subset of C is paired to a unique 5-digit binary number, and every 5-digit binary number represents a unique subset of C. If an element of C is not present in the subset, there is a 0 in some position of the number. If an element of C is present in the subset, there is a 1 in the same position. The number 00000 represents the subset of C with no elements -- the empty set -- a subset that is present in all sets.

    BTW, this question should have gone into one of the mathematics sections, either Precalculus or Calculus and Beyond.
     
  6. Jan 12, 2010 #5
    I really don't know where to post it..~ due to this question is found in my INTRODUCTION TO THE THEORY OF COMPUTATION ..~ so i assume it is under this section..
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook