Power set

The empty set. The only subset of \varnothing is \varnothing itself: a subset of \varnothing can have no members. So \mathcal{P}(\varnothing) = \{\varnothing\}. This set is not empty. It has one member, and that member happens to be the empty set.

Counting, first proof: strings. Proof. List the members of A as a_1, a_2, \dots, a_n. Send each subset X to the string b_1 b_2 \cdots b_n, where b_i = 1 if a_i \in X and b_i = 0 if a_i \notin X. Two different subsets differ about some member a_i, so their strings differ in place i. Every string comes from a subset, namely the set of those a_i with b_i = 1. So subsets and strings are matched one to one, and there are as many subsets as strings. A string is built in n stages with two choices at each, so by the fundamental counting principle there are 2 \cdot 2 \cdots 2 = 2^n strings. \square

Counting, second proof: doubling. Proof. We use induction on n. For n = 0 the set is \varnothing, and \lvert \mathcal{P}(\varnothing)\rvert = 1 = 2^0. Now suppose every set with n members has 2^n subsets, and let A have n + 1 members. Choose one member a, and let A' be the set of the other n members. The subsets of A fall into two groups.

• Those without a. These are exactly the subsets of A', so there are 2^n of them.
• Those with a. Removing a from such a subset leaves a subset of A', and adding a to a subset Y of A' gives Y \cup \{a\}, a subset with a. These two moves undo each other, so this group is matched one to one with the subsets of A' and also has 2^n members.

No subset is in both groups, so A has 2^n + 2^n = 2^{n + 1} subsets. \square

The first proof counts all the subsets at once. The second says what one new member does, which is often the more useful fact: it is the dashed lines of Figure 1.

Power sets keep inclusion. Proof. Suppose A \subseteq B, and let X \in \mathcal{P}(A). Then X \subseteq A and A \subseteq B, so X \subseteq B because inclusions chain, and X \in \mathcal{P}(B). For the converse, suppose \mathcal{P}(A) \subseteq \mathcal{P}(B). Since A \subseteq A, we have A \in \mathcal{P}(A), so A \in \mathcal{P}(B), which says A \subseteq B. \square

Intersections. Proof. For any set X, the following conditions are equivalent.

The first and last steps are the definitions of power set and intersection. For the middle step: if X \subseteq A \cap B, each x \in X is in both A and B, so X \subseteq A and X \subseteq B; and if X \subseteq A and X \subseteq B, each x \in X is in both, so in A \cap B. Every step goes both ways, so the two sets have the same members. \square

Unions. Proof. Let X \in \mathcal{P}(A) \cup \mathcal{P}(B). Then X \subseteq A or X \subseteq B. In the first case, X \subseteq A \subseteq A \cup B; in the second, X \subseteq B \subseteq A \cup B. Either way X \in \mathcal{P}(A \cup B). \square

The reverse inclusion fails as soon as A and B are two different one-member sets, say A = \{r\} and B = \{s\}. Then \{r, s\} \subseteq A \cup B, so \{r, s\} \in \mathcal{P}(A \cup B), but \{r, s\} is a subset of neither A nor B. A subset of a union may take some members from each part, and such a subset belongs to neither power set.

1. \varnothing, \{5\}, \{10\}, \{5, 10\}: four members, 2^2 = 4.
2. \{w, x\}, \{w, y\}, \{w, z\}, \{x, y\}, \{x, z\}, \{y, z\}: six of them.
3. \mathcal{P}(B) = \{\varnothing, \{1\}, \{\{2\}\}, \{1, \{2\}\}\}. The two members of B are 1 and \{2\}, and a subset takes neither, one or both. The set \{2\} is not a subset of B, because 2 \notin B.
4. (a) True, \{3, 5\} \subseteq A. (b) False, 4 is a number, not a subset of A. (c) True, its one member \varnothing is in \mathcal{P}(A). (d) False, its member 4 is not in \mathcal{P}(A). (e) True, both \{3\} and \{4, 5\} are subsets of A. (f) True.
5. Not a member, but a subset. \mathcal{P}(\mathcal{P}(\varnothing)) = \{\varnothing, \{\varnothing\}\}, and \{\{\varnothing\}\} is neither of these two sets. Its one member \{\varnothing\} is a member of \mathcal{P}(\mathcal{P}(\varnothing)), so it is a subset.
6. A \cap \mathcal{P}(A) = \{\{1\}\}. The member \{1\} of A is a subset of A because 1 \in A. The member 1 is not a set, so it is not in \mathcal{P}(A).
7. 2^{10} = 1{,}024.
8. 12, since 2^{12} = 4{,}096.
9. \mathcal{P}(A) has 2^3 = 8 members, so \mathcal{P}(\mathcal{P}(A)) has 2^8 = 256.
10. The places holding 1 are 2, 3, 5 and 8, so the subset is \{2, 3, 5, 8\}. The set \{1, 8\} is named by 10000001.
11. 2^7 = 128: such a subset is any subset of \{4, 5, \dots, 10\}, which has 7 members.
12. 5. If \lvert A\rvert = n, the difference is 2^{n + 1} - 2^n = 2^n, and 2^n = 32 gives n = 5.
13. \{\varnothing, \{3\}\}. These are the only sets that are subsets of both, and A \cap B = \{3\} has power set \{\varnothing, \{3\}\}.
14. \lvert \mathcal{P}(A) \cup \mathcal{P}(B)\rvert = 8 + 4 - 2 = 10 and \lvert \mathcal{P}(A \cup B)\rvert = 2^4 = 16. One member in neither is \{1, 4\}, which takes 1 from A only and 4 from B only.
15. For example A = \{1\} and B = \{1, 2\}. Since A \subseteq B, both sides equal \mathcal{P}(B), by Example 5.
16. \{\varnothing\}. It equals \mathcal{P}(A \cap B) = \mathcal{P}(\varnothing), and the only set inside both A and B is \varnothing.
17. Since \mathcal{P}(A) \subseteq \mathcal{P}(B), power sets keeping inclusion gives A \subseteq B; since \mathcal{P}(B) \subseteq \mathcal{P}(A), it gives B \subseteq A. By double inclusion, A = B. \square
18. \varnothing \subseteq A for every set A, so \varnothing \in \mathcal{P}(A). If A has a member a, then \{a\} \subseteq A is a second member, different from \varnothing. So one member only happens when A has no members, and then \mathcal{P}(\varnothing) = \{\varnothing\}.
19. Let A' be A without a, with m members. The doubling argument splits the subsets of A into those without a, which are the 2^m subsets of A', and those with a, matched one to one with the same 2^m sets by Y \mapsto Y \cup \{a\}. The two groups are the same size, so each is half of the 2^{m + 1} subsets.
20. Let Z \in \mathcal{P}(A \cup B), so Z \subseteq A \cup B. Take X = Z \cap A and Y = Z \cap B. Then X \subseteq A and Y \subseteq B. Every z \in Z is in A or in B, so in X or in Y; and X and Y lie inside Z. So Z = X \cup Y. \square