1. Limited time only! Sign up for a free 30min personal 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!

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