Discrete math, sets, power sets.

[sg001]

Homework Statement

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

Homework Equations

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 isn't the case... can some one explain why... what it is it that I'm not getting?

 

[mtayab1994]

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

 

[sg001]

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

 

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

 

[mtayab1994]

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

 

[sg001]

okie...
Thanks for the quick reply!

 

[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 = 2⁰.

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.

 

[mtayab1994]

To simplify it more for you just look in the link:

http://www.proofwiki.org/wiki/Cardinality_of_Power_Set