Powersets

The powerset of a set S is the set of all S's subsets. 

The elements of a powerset are themselves sets, always (because each element is a subset of S). 

We write the powerset of a set S as (S) or P (S) or 2S (I'm going to use because it's easier to do in HTML).  The is a script P (for "powerset").  You will see below why 2S is a plausible notation. 

Here are some examples, using a, b, c, ... as elements: 

()
{ } (the set whose only element is the empty set).
The empty set is a subset of every set, so is in every powerset. 
({a})
{, {a} }
{a} is present because it is a subset of itself — every set is a subset of itself.  Recall that the "subset" relation is actually "subset or equal to". 
({a, b})
{, {b}, {a}, {a,b} }. 
Notice that the elements of the powerset correspond to 00, 01, 10, 11 (how?).
({a, b, c})
{, {c}, {b}, {b,c}, {a}, {a,c}, {a,b}, {a,b,c} }. 
Notice that the elements of the powerset correspond to 000, 001, 010, 011, 100, 101, 110, 111.
({a, b, c, d})
{, {d}, {c}, {c,d}, {b}, {b,d}, {b,c}, {b,c,d}, {a}, {a,d}, {a,c}, {a,c,d}, {a,b}, {a,b,d}, {a,b,c}, {a,b,c,d} }. 
Notice that the elements of the powerset correspond to 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111. 

A larger example is given below. 

Powersets and binary integers

The elements of the powerset of a set of n elements correspond to the n-bit binary integers from 0 to (2n-1): 

Thus we can enumerate the elements of a powerset by counting from 0 to (2n-1) and for each number giving the subset containing the elements corresponding to the 1 bits. 

Partially ordered sets and powersets

The elements of a powerset have a natural ordering, , and any powerset and form a It is an ordered set because the elements have an order, and a partially ordered set (rather than a totally ordered set) because not all pairs of elements are ordered.  For example, look at

Some pairs of elements of ({a,b}) are ordered, such as {b} and {b}{a,b}.  But {a} and {b} are not ordered by , because neither {a}{b} nor {b}{a}.  That means ({a,b}) is a partially ordered set. 

Lattices and powersets

lattice for integers

Figure 1
A diagram of the lattice for
a powerset — ({a,b,c})

Any powerset is also a lattice because

  1. it is a partially ordered set, and
  2. each pair of elements has a least upper bound (LUB) and a greatest lower bound (GLB). 

Let's talk about the LUB part. 

  1. The union of two elements is an upper bound for them, because for any two sets S and T, SST. 
  2. The union of two elements is the least upper bound for S and T because there is no set R smaller than ST that contains both S and T. 

The same argument supports the statement that the GLB is their intersection, if you substitute "intersection" for "union" and "lower" for "upper".  (This is an example of the duality of union and intersection, and of LUB and GLB.) 

The powerset of {a, b, c, d, e, f, g}

Below is a larger example, a list of the elements of the powerset of {a, b, c, d, e, f, g}.  The set has 7 elements so its powerset has 27 = 128 elements.  This list was generated by a program. 

  1. {}
  2. {g}
  3. {f}
  4. {f,g}
  5. {e}
  6. {e,g}
  7. {e,f}
  8. {e,f,g}
  9. {d}
  10. {d,g}
  11. {d,f}
  12. {d,f,g}
  13. {d,e}
  14. {d,e,g}
  15. {d,e,f}
  16. {d,e,f,g}
  17. {c}
  18. {c,g}
  19. {c,f}
  20. {c,f,g}
  21. {c,e}
  22. {c,e,g}
  23. {c,e,f}
  24. {c,e,f,g}
  25. {c,d}
  26. {c,d,g}
  27. {c,d,f}
  28. {c,d,f,g}
  29. {c,d,e}
  30. {c,d,e,g}
  31. {c,d,e,f}
  32. {c,d,e,f,g}
  33. {b}
  34. {b,g}
  35. {b,f}
  36. {b,f,g}
  37. {b,e}
  38. {b,e,g}
  39. {b,e,f}
  40. {b,e,f,g}
  41. {b,d}
  42. {b,d,g}
  43. {b,d,f}
  44. {b,d,f,g}
  45. {b,d,e}
  46. {b,d,e,g}
  47. {b,d,e,f}
  48. {b,d,e,f,g}
  49. {b,c}
  50. {b,c,g}
  51. {b,c,f}
  52. {b,c,f,g}
  53. {b,c,e}
  54. {b,c,e,g}
  55. {b,c,e,f}
  56. {b,c,e,f,g}
  57. {b,c,d}
  58. {b,c,d,g}
  59. {b,c,d,f}
  60. {b,c,d,f,g}
  61. {b,c,d,e}
  62. {b,c,d,e,g}
  63. {b,c,d,e,f}
  64. {b,c,d,e,f,g}
  65. {a}
  66. {a,g}
  67. {a,f}
  68. {a,f,g}
  69. {a,e}
  70. {a,e,g}
  71. {a,e,f}
  72. {a,e,f,g}
  73. {a,d}
  74. {a,d,g}
  75. {a,d,f}
  76. {a,d,f,g}
  77. {a,d,e}
  78. {a,d,e,g}
  79. {a,d,e,f}
  80. {a,d,e,f,g}
  81. {a,c}
  82. {a,c,g}
  83. {a,c,f}
  84. {a,c,f,g}
  85. {a,c,e}
  86. {a,c,e,g}
  87. {a,c,e,f}
  88. {a,c,e,f,g}
  89. {a,c,d}
  90. {a,c,d,g}
  91. {a,c,d,f}
  92. {a,c,d,f,g}
  93. {a,c,d,e}
  94. {a,c,d,e,g}
  95. {a,c,d,e,f}
  96. {a,c,d,e,f,g}
  97. {a,b}
  98. {a,b,g}
  99. {a,b,f}
  100. {a,b,f,g}
  101. {a,b,e}
  102. {a,b,e,g}
  103. {a,b,e,f}
  104. {a,b,e,f,g}
  105. {a,b,d}
  106. {a,b,d,g}
  107. {a,b,d,f}
  108. {a,b,d,f,g}
  109. {a,b,d,e}
  110. {a,b,d,e,g}
  111. {a,b,d,e,f}
  112. {a,b,d,e,f,g}
  113. {a,b,c}
  114. {a,b,c,g}
  115. {a,b,c,f}
  116. {a,b,c,f,g}
  117. {a,b,c,e}
  118. {a,b,c,e,g}
  119. {a,b,c,e,f}
  120. {a,b,c,e,f,g}
  121. {a,b,c,d}
  122. {a,b,c,d,g}
  123. {a,b,c,d,f}
  124. {a,b,c,d,f,g}
  125. {a,b,c,d,e}
  126. {a,b,c,d,e,g}
  127. {a,b,c,d,e,f}
  128. {a,b,c,d,e,f,g}
Valid XHTML 1.0 Strict
Valid CSS!
2010Feb24We20:57
Thomas A. Alspaugh