# Discrete math, sets, power sets.

1. Mar 1, 2012

### sg001

1. The problem statement, all variables and given/known data

If s (0,1), find
|P(S)|, |P(P(S))|, |P(P(P(S)))|

2. Relevant equations

3. The attempt at a solution

|P(S)| = {(0), (1), (0,1), ∅} = 4

|P(P(S))| = {.........} = 16.

|P (P(P(S)))| = {......} = 16 ^4 ....but how?

as my lecturer explained it, it come from pascals triangle
where the number of elements in the original set corresponds to the number from the triangle. So far so good, so in |P(S)| it contains 4 elements as shown above. Hence |P(P(S))| is equal to the sum of the corresponding (4) row of the triangle (1,4,6,4,1) = 16.

But from this logic |P(P(P(S)))| should equal the sum of the (16) expansion, but this isnt the case... can some one explain why... what it is it that i'm not getting???

2. Mar 1, 2012

### mtayab1994

from what i know lP(S)l=2^n

3. Mar 1, 2012

### sg001

Correct, I only just realised it... does this come from binomial theorem?

4. Mar 1, 2012

### mtayab1994

I don't know why you would bring up binomial theorem? If you use that property of 2^n you should be able to easily solve lP(P(S)l and so on.

5. Mar 1, 2012

### mtayab1994

It's used to prove the "power rule".

6. Mar 1, 2012

okie...

7. Mar 1, 2012

### Deveno

two approaches to proving |P(A)| = 2|A|, for a finite set A.

approach 1: induction on |A|.

if |A| = 0, A is the empty set, in which case P(∅) = {∅} so |P(∅)| = 1 = 20.

assume that |P(A)| = 2|A|, whenever |A| < n.

now pick an element a in A. consider P(A-{a}). what sets are in P(A) that aren't in P(A-{a})? the sets containing a, right?

show that every set in P(A) that contains a is equal to BU{a}, where B is in P(A-{a}). conclude there is a bijection from the sets of P(A) containing a to P(A-{a}).

approach 2: just count.

there are nCk ways to pick k elements of A, if |A| = n, where:

nCk = n!/(k!(n-k)!)

so we have:

nCn (=1) subsets of A with n elements, namely A
nC(n-1) subsets of A with n-1 elements
.....
nC2 subsets of A with 2 elements
nC1 = n subsets of A with 1 element, namely the sets {a} with a in A,
nC0 = 1 subset of A with no elements, namely, the empty set.

now add these together (these are the numbers in the n-th row of pascal's triangle).

of course, to prove:

$$\sum_{k=0}^n \begin{pmatrix}n\\k \end{pmatrix} = 2^n$$

you'll probably have to use induction.

8. Mar 1, 2012