- Practice
- About 14 min
- 5 practice questions
Subsets and power sets: counting fast
Answer subset and power-set questions in seconds: nested brackets, conditional subset counts, power sets of power sets and equations in 2^n.
If something looks wrong, please tell us.
Subset questions in competitive exams come in a few fixed shapes: decide which of four membership statements is true, count subsets with some elements forced in or out, find n(P(P(∅))), or find the sizes of two sets from the difference in their numbers of subsets. Each shape has a quick method. This lesson sets them out with the reasoning behind each, so that you can work fast without guessing.
∈ or ⊆: test the brackets
To test x ∈ A, look for x written as one complete element in the list of A. To test X ⊆ A, take each element of X in turn and check that it is in A. With A = {1, {1, 2}, 3}, the statement {1, 2} ∈ A is true, because {1, 2} is listed as an element. But {1, 2} ⊆ A is false, since 2 by itself is not an element of A. Meanwhile {1, 3} ⊆ A and {{1, 2}} ⊆ A are both true. Treat every inner bracket as a sealed box: you may take the whole box but not its contents.
Conditional subset counts
Each element of a set has two choices, in or out, which gives 2^n subsets in total. When a question forces some elements in or keeps some out, those elements lose their choice, and only the free elements contribute a factor of 2. So if n elements are free, there are 2^n subsets. Read the conventions too: 'subsets' includes ∅ and the set itself; 'proper subsets' excludes the set itself (2^n − 1); 'non-empty proper subsets' excludes both (2^n − 2).
Worked example 1: forced and forbidden elements
How many subsets of {1, 2, 3, 4, 5, 6} contain both 1 and 2 but not 6? Elements 1 and 2 are forced in and 6 is forced out, so they have no choice. The free elements are 3, 4 and 5. Each is in or out, so the count is 2^3 = 8. Listing confirms it: start with {1, 2} and add any subset of {3, 4, 5}, of which there are 8.
Worked example 2: power set of a power set
Find n(P(P(∅))). Build from the inside. ∅ has 0 elements, so P(∅) = {∅}, which has 2^0 = 1 element. Then P({∅}) has 2^1 = 2 elements, namely ∅ and {∅}. So n(P(P(∅))) = 2. Repeating once more, P(P(P(∅))) has 2^2 = 4 elements. The rule is to apply 2^n one layer at a time, using the size of the layer just found.
Worked example 3: the difference of subset counts
A has m elements and B has n elements, and A has 56 more subsets than B. Find m and n. Write 2^m − 2^n = 56 and take out the smaller power: 2^n(2^(m − n) − 1) = 56 = 8 × 7. The bracket is odd, so 2^n must be the whole power of 2 in 56, which is 8, giving n = 3. Then 2^(m − n) − 1 = 7, so 2^(m − n) = 8 and m − n = 3, giving m = 6. Check: 64 − 8 = 56. Splitting the number into a power of 2 times an odd number makes the answer unique.
Subset facts that shorten working
- A ⊆ B and B ⊆ C together give A ⊆ C.
- A ⊆ B is the same as A ∩ B = A, and the same as A ∪ B = B.
- A = B exactly when A ⊆ B and B ⊆ A.
- ∅ ⊆ A for every A, but ∅ ∈ A only if ∅ is listed as an element of A.
These equivalences are often tested in reverse: if you are told A ∪ B = B, you may conclude A ⊆ B, and then A ∩ B = A and A − B = ∅ follow at once.
Forced-in and forced-out elements have no choice; each free element doubles the count, so k free elements give 2^k subsets. For 2^m − 2^n = N, write N as (power of 2) × (odd number).
Key takeaways
Treat an inner set as one sealed element when testing ∈ and ⊆. Count conditional subsets with free elements only. Build power sets of power sets one layer at a time. Split the difference of two powers of 2 into a power of 2 times an odd number. And always check whether the question counts the empty set and the set itself.
Check your understanding
-
1. What is n(P(P(∅)))?
- 1
- 2
- 0
- 4
Show answer
Answer: B. P(∅) = {∅} has 1 element, so its power set has 2^1 = 2 elements: ∅ and {∅}.
-
2. How many subsets of {a, b, c, d, e} contain a but not b (the set itself and ∅ are counted if they qualify)?
- 16
- 8
- 4
- 32
Show answer
Answer: B. a is forced in and b forced out; c, d and e are free, so there are 2^3 = 8 subsets.
-
3. Set A has 112 more subsets than set B. How many elements does A have?
- 6
- 7
- 8
- 4
Show answer
Answer: B. 2^m − 2^n = 112 = 16 × 7, so 2^n = 16 (n = 4) and 2^(m − n) − 1 = 7, so m − n = 3 and m = 7. Check: 128 − 16 = 112.
-
4. Let A = {1, {1, 2}, 3}. Which statement is false?
- {1, 2} ⊆ A
- {1, 2} ∈ A
- {1, 3} ⊆ A
- {{1, 2}} ⊆ A
Show answer
Answer: A. {1, 2} ⊆ A would need 2 ∈ A, but 2 is not an element of A on its own. The other three statements are true.
-
5. If A ⊆ B, then A ∩ B is always equal to
- A
- B
- ∅
- A ∪ B
Show answer
Answer: A. Every element of A is in B, so the common part is all of A: A ∩ B = A. (A ∪ B equals B, not A.)
Sign in to keep track of the lessons you finish.