How many copies of curly braces occur in the expanded notation for Ƥ⁵(Ø), in the representation where an empty set appears as Ø ?

(Hint: see Binary nature of power set)

Answer:

Let C(Ƥⁿ(Ø)) be the number of elements in Ƥⁿ(Ø)
Let B(Ƥⁿ(Ø)) be the number of curly braces occurrence in Ƥⁿ(Ø)

Based on the observation in the Binary nature of power set,

1. when n > 0, C(Ƥⁿ(Ø)) = 2^C(Ƥn-1(Ø))
   
2. when n > 1, every element in Ƥ^n-1(Ø) is included in exactly half of all the element sets in Ƥⁿ(Ø)
   
3. every element in a non-empty power set is a set and therefore has an outer pair of curly braces except the element Ø
   
4. a non-empty power set always has exactly one pair of outer most curly braces
   

This translates to:

  B(Ƥn(Ø)) = (B(Ƥn-1(Ø)) - 1) · C(Ƥn(Ø))/2 + C(Ƥn(Ø)) where n > 1

  Ƥ0(Ø) ≡ Ø
  Ƥ1(Ø) ≡ {Ø}
  Ƥ2(Ø) ≡ {Ø,{Ø}}
  Ƥ3(Ø) ≡ {Ø,{Ø},{{Ø}},{Ø,{Ø}}}
  ...

  C(Ƥ0(Ø)) = 0
  C(Ƥ1(Ø)) = 2C(Ƥ0(Ø)) = 1
  C(Ƥ2(Ø)) = 2C(Ƥ1(Ø)) = 2
  C(Ƥ3(Ø)) = 2C(Ƥ2(Ø)) = 4
  C(Ƥ4(Ø)) = 2C(Ƥ3(Ø)) = 16
  C(Ƥ5(Ø)) = 2C(Ƥ4(Ø)) = 65536

  B(Ƥ1(Ø)) = 1
  B(Ƥ2(Ø)) = (B(Ƥ1(Ø)) - 1) · C(Ƥ2(Ø))/2 + C(Ƥ2(Ø)) = 0 + 2 = 2
  B(Ƥ3(Ø)) = (B(Ƥ2(Ø)) - 1) · C(Ƥ3(Ø))/2 + C(Ƥ3(Ø)) = 1 · 4 /2 + 4 = 6
  B(Ƥ4(Ø)) = (B(Ƥ3(Ø)) - 1) · C(Ƥ4(Ø))/2 + C(Ƥ4(Ø)) = 5 · 16 /2 + 16 = 56
  B(Ƥ5(Ø)) = (B(Ƥ4(Ø)) - 1) · C(Ƥ5(Ø))/2 + C(Ƥ5(Ø)) = 55 · 65536 /2 + 65536 = 1867776

So there are 1,867,776 copies of curly braces occur in the expanded notation for Ƥ⁵(Ø)

How many copies of Ø occur in the expanded notation for Ƥ⁵(Ø) ?

(Hint: see Binary nature of power set)

Answer:

Let C(Ƥⁿ(Ø)) be the number of elements in Ƥⁿ(Ø)
Let E(Ƥⁿ(Ø)) be the number of Ø occurrence in Ƥⁿ(Ø)

Based on the observation in the Binary nature of power set,

1. when n > 0, C(Ƥⁿ(Ø)) = 2^C(Ƥn-1(Ø))
   
2. when n > 1, every element in Ƥ^n-1(Ø) is included in exactly half of all the element sets in Ƥⁿ(Ø)
   
3. there always exists an empty set in a non-empty power set
   

This translates to:

  E(Ƥn(Ø)) = E(Ƥn-1(Ø)) · C(Ƥn(Ø))/2 + 1 where n > 1

  Ƥ0(Ø) ≡ Ø
  Ƥ1(Ø) ≡ {Ø}
  Ƥ2(Ø) ≡ {Ø,{Ø}}
  Ƥ3(Ø) ≡ {Ø,{Ø},{{Ø}},{Ø,{Ø}}}
  ...

  C(Ƥ0(Ø)) = 0
  C(Ƥ1(Ø)) = 2C(Ƥ0(Ø)) = 1
  C(Ƥ2(Ø)) = 2C(Ƥ1(Ø)) = 2
  C(Ƥ3(Ø)) = 2C(Ƥ2(Ø)) = 4
  C(Ƥ4(Ø)) = 2C(Ƥ3(Ø)) = 16
  C(Ƥ5(Ø)) = 2C(Ƥ4(Ø)) = 65536

  E(Ƥ1(Ø)) = 1
  E(Ƥ2(Ø)) = E(Ƥ1(Ø)) · C(Ƥ2(Ø))/2 + 1 = 1 · 2 /2 + 1 = 2
  E(Ƥ3(Ø)) = E(Ƥ2(Ø)) · C(Ƥ3(Ø))/2 + 1 = 2 · 4 /2 + 1 = 5
  E(Ƥ4(Ø)) = E(Ƥ3(Ø)) · C(Ƥ4(Ø))/2 + 1 = 5 · 16 /2 + 1 = 41
  E(Ƥ5(Ø)) = E(Ƥ4(Ø)) · C(Ƥ5(Ø))/2 + 1 = 41 · 65536 /2 + 1 = 1343489

So there are 1,343,489 copies of Ø occur in the expanded notation for Ƥ⁵(Ø)

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

To connect to the router:

  http://192.168.1.1

To vnc to another mac:

  Enable "Screen Sharing" on the target mac, and enter vnc://192.168.1.x in Safari

Given Ƥ, the power set function, and Ø, the empty set,what are Ƥ(Ø), Ƥ(Ƥ(Ø)) and Ƥ(Ƥ(Ƥ(Ø))) ?
How many members are there in Ƥ4(Ø) and Ƥ5(Ø) ?

Answers:
Ƥ1(Ø) = {Ø}                     cardinality: 20 = 1
Ƥ2(Ø) = {Ø,{Ø}}                 cardinality: 21 = 2
Ƥ3(Ø) = {Ø,{Ø},{{Ø}},{Ø,{Ø}}}   cardinality: 22 = 4
Ƥ4(Ø) = {
          Ø,
          {Ø},
          {{Ø}},
          {{{Ø}}},
          {Ø,{Ø}},
          {Ø,{{Ø}}},
          {{Ø,{Ø}}},
          {{Ø},{{Ø}}},
          {Ø,{Ø,{Ø}}},
          {Ø,{Ø},{{Ø}}},
          {{Ø},{Ø,{Ø}}},
          {{{Ø}},{Ø,{Ø}}},
          {Ø,{Ø},{Ø,{Ø}}},
          {Ø,{{Ø}},{Ø,{Ø}}},
          {{Ø},{{Ø}},{Ø,{Ø}}},
          {Ø,{Ø},{{Ø}},{Ø,{Ø}}}
        }                       cardinality: 24 = 16

There are 216 members in Ƥ5(Ø)