Question

If |A| =n then | p ( P(A))| = ? Justify your answer.

Answer 1

|A|=n then |P(A)|=2^n |P(P(A))|=2^(2^n) Eg : Suppose our original set is A = {a,b} The power set of this is the set of all subsets: P(A) = { {}, No elements {a}, {b}, One element {a,b} Two elements } To make subsequent expansion less of a notational nightmare, I'm going to use variables to represent these subsets, i.e., P(A) = { W, X, Y, Z } Now we can take the power set of the power set, which is the set of all subsets of P(A): P(P(A)) = { {}, No elements {W}, One element {X}, {Y}, {Z}, {W,X}, Two elements {W,Y}, {W,Z}, {X,Y}, {X,Z}, {Y,Z}, {W,X,Y}, Three elements {W,X,Z}, {W,Y,Z}, {X,Y,Z}, {W,X,Y,Z} Four elements } This is 2^4 = 16 elements, as we would expect. To express them in terms of the original elements, we can substitute as needed: W -> {} X -> {a} Y -> {b} Z -> {a,b} P(P(A)) = { {}, {{}}, {{a}}, {{b}}, {{a,b}}, {{},{a}}, {{},{b}}, {{},{a,b}}, {{a},{b}}, {{a},{a,b}}, {{b},{a,b}}, {{},{a},{b}}, {{},{a},{a,b}}, {{},{b},{a,b}}, {{a},{b},{a,b}}, {{},{a},{b},{a,b}} }