Exploring Power Sets and Cartesian Products: Explaining the Answers

[RyozKidz]

Homework Statement

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

Homework Equations

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

 

[CompuChip]

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?

 

[RyozKidz]

o..~ nice explanation ..~ 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 ?

 

[Mark44]

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.

 

[RyozKidz]

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