Higher Mathematics · Classes 9-10 · Chapter 1

Power Set.

How many subsets does a three-element set have? Count by hand and almost everyone drops one, usually ∅ or the whole set. By the end of this note you will not count at all: one rule does it.

1. A set of subsets

The set of all subsets of A is called the power set of A, written P(A). Its elements are themselves sets. So B ∈ P(A) says that B is a subset of A, that is, B ⊆ A.

Two members are always in it. Since ∅ ⊆ A, ∅ belongs to P(A) for every A. Since A ⊆ A, A itself belongs too. These are exactly the two people forget when they list subsets by hand.

The book's table, from the smallest set up:
A = ∅ gives P(A) = {∅}
A = {a} gives P(A) = {∅, A}
A = {a, b} gives P(A) = {∅, {a}, {b}, A}
A = {a, b, c} gives P(A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, A}
Now build one yourself: choose how many elements, tap chips to make a subset, then add it to the box.

2. The counting rule

In the table, 0, 1, 2, 3 elements give 1, 2, 4, 8 subsets. Each new element doubles the count, because every earlier subset can be made with it or without it. So if n(A) = n, A has 2ⁿ subsets, which means P(A) has 2ⁿ elements.

A proper subset is any subset except A itself, and the book counts ∅ as one. So a set of n elements has 2ⁿ − 1 proper subsets: 7 for three elements, 15 for four, 3 for {2, 3}, 1 for {1}. In the box above the whole set greys out and is left out of the proper count.

A set of 2n elements has 2²ⁿ = (2²)ⁿ = 4ⁿ subsets, so statement (i) of Exercise 1.1 No.1 is true.

When a set is given by a condition, list it first to find n, then use 2ⁿ. A = {x ∈ N : 6 < 2x < 17} = {4, 5, 6, 7, 8}, so n = 5 and n(P(A)) = 2⁵ = 32. A = {x ∈ Z : 9 ≤ x² ≤ 36} = {±3, ±4, ±5, ±6}, so n = 8 and 2⁸ = 256. Check them in the calculator below.

3. The power sets of two sets

Example 6: A = {a, b}, B = {b, c}. Then P(A) ∪ P(B) = {∅, {a}, {b}, {c}, {a, b}, {b, c}}, only six. And A ∪ B = {a, b, c}, so P(A ∪ B) has eight elements. All six are among the eight, so P(A) ∪ P(B) ⊆ P(A ∪ B). They are not equal, because {a, c} and {a, b, c} are missing. Drag the handle and see.

Intersection behaves differently. A set that is a subset of both A and B is a subset of A ∩ B, so P(A) ∩ P(B) = P(A ∩ B). Activity: with A = {1, 2}, B = {2, 5}, both sides are {∅, {2}}. And P(A) ∪ P(B) lacks {1, 2, 5}, so P(A) ∪ P(B) ≠ P(A ∪ B).

4. Two small cases

P(∅) = {∅}, with one element. And P({∅}) = {∅, {∅}}, with two elements. The set {∅} has exactly one element, namely ∅, so the rule gives 2¹ = 2.

Activity: with A = {1, 2, 3}, B = {1, 2}, C = {2, 3}, D = {1, 3}, P(A) = {A, B, C, D, {1}, {2}, {3}, ∅}. Count them: three one-element sets, three two-element sets, plus ∅ and A, 8 in all.

5. Check yourself

Three questions: put the counting rule to work.

In the second, write the set out from its condition first.

In the last, remember ∅ and the whole set.

The whole note on seven cards.

Source: Higher Mathematics, Classes 9-10 (NCTB), Chapter 1 “Set and Function”, the “Power Set” part.