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

— Rule to remember

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. 1. What is n(P(P(∅)))?

    1. 1
    2. 2
    3. 0
    4. 4
    Show answer

    Answer: B. P(∅) = {∅} has 1 element, so its power set has 2^1 = 2 elements: ∅ and {∅}.

  2. 2. How many subsets of {a, b, c, d, e} contain a but not b (the set itself and ∅ are counted if they qualify)?

    1. 16
    2. 8
    3. 4
    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. 3. Set A has 112 more subsets than set B. How many elements does A have?

    1. 6
    2. 7
    3. 8
    4. 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. 4. Let A = {1, {1, 2}, 3}. Which statement is false?

    1. {1, 2} ⊆ A
    2. {1, 2} ∈ A
    3. {1, 3} ⊆ A
    4. {{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. 5. If A ⊆ B, then A ∩ B is always equal to

    1. A
    2. B
    3. ∅
    4. 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.)

Privacy · Terms · Refunds · Delivery