Observe the implementation of a power list in Haskell:

powerList :: [a] -> [[a]]
powerList [] = [[]]
powerList (x:xs) = (powerList xs) ++ (map (x:) (powerList xs))

If A contains N elements, the generation of the power list of A grows as a list that gets doubled on every element. This is rather obvious by examining the algorithm above, and explains why the cardinality of Ƥ(A) = 2^N.

What's interesting but perhaps less obvious is that every element of A always ends up being included in half of all the lists in the power list of A. For example, if there are 4 elements in A, the power list of A will have 2^4=16 lists, and every element in A will be included in exactly 8 of those 16 lists.

And clearly, a power list always contains an empty list as an element, except in the case when the power list per se is the empty list.

Here is a more visual illustration of the double-up behavior in generating the power list of [4,3,2,1]. ie

 powerList [4,3,2,1]

would yield the output:

[[],[1],[2],[2,1],[3],[3,1],[3,2],[3,2,1],[4],[4,1],[4,2],[4,2,1],[4,3],[4,3,1],[4,3,2],[4,3,2,1]]

annotated below:

[
 [],                <-| <-| <-| <-|
 ----- 1st double up -|   |   |   |
 [1],               <-|   |   |   |
 --------- 2nd double up -|   |   |
 [2],                     |   |   |
 [2,1],                 <-|   |   |
 ------------- 3rd double up -|   |
 [3],                         |   |
 [3,1],                       |   |
 [3,2],                       |   |
 [3,2,1],                   <-|   |
 ----------------- 4th double up -|
 [4],                             |
 [4,1],                           |
 [4,2],                           |
 [4,2,1],                         |
 [4,3],                           |
 [4,3,1],                         |
 [4,3,2],                         |
 [4,3,2,1]                      <-|
]

Another interesting observation from the definition of a power set is that:

2^n = nC0 + nC1 + ... + nCn