Powersets thomasalspaugh.org/pub/fnd/powerset.html

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 2^S (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 2^S 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 (2ⁿ-1): 

• the ith bit corresponds to the presence or absence of the ith element. 

Thus we can enumerate the elements of a powerset by counting from 0 to (2ⁿ-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

• ℘({a, b}) = {∅, {b}, {a}, {a,b} }

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

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

• The LUB is the union of the two elements.
• The GLB is their intersection.

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, S⊆S∪T. 
2. The union of two elements is the least upper bound for S and T because there is no set R smaller than S∪T 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 2⁷ = 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}

Thomas A. Alspaugh alspaugh  at · ics · uci · edu