Skip to content
Tutorials Center
My learning

Topics

Lesson 3 of 38 ยท Getting Started

Power Sets and Counting Subsets

Learn the power set P(A), why a set with n elements has 2^n subsets, and how binary strings list every subset, with runnable Python code.

Take a set and gather all of its subsets into a new set. The result is called the power set. It is a simple idea with a big payoff: counting subsets leads to the formula 2โฟ, and later in this track the power set will be the key to proving that some infinities are larger than others.

Definition

The power set of A, written P(A) (or ๐’ซ(A) or 2^A), is the set of all subsets of A:

Text
P(A) = { S : S โІ A }

Remember that โˆ… โІ A and A โІ A, so both the empty set and A itself are always elements of P(A).

Example. For A = {a, b} the subsets are โˆ…, , and {a, b}, so

Text
P({a, b}) = { โˆ…, {a}, {b}, {a, b} }

Notice that P(A) is a set whose elements are sets. It has 4 elements here, even though A has 2.

The empty set versus the set containing it

Because power sets contain the empty set, they are a good place to practice the difference between โˆ… and {โˆ…}:

  • P(โˆ…) = {โˆ…}. The empty set has exactly one subset, itself. So P(โˆ…) has 1 element.
  • P({โˆ…}) = {โˆ…, {โˆ…}}, which has 2 elements.

Applying P again and again produces sets of sizes 1, 2, 4, 16, 65536, ... which grows astonishingly fast.

How many subsets? The 2โฟ rule

If |A| = n then |P(A)| = 2โฟ. Here is the reason. To build a subset of A, go through the elements one by one and decide, for each, in or out. There are 2 choices for each of the n elements, and the choices are independent, so there are 2 ร— 2 ร— ... ร— 2 = 2โฟ ways in total. Each pattern of choices gives a different subset.

n Subsets of A Count
0 โˆ… only 1
1 โˆ…, 2
2 add b to each of the above or not 4
3 double again 8

Another way to see the doubling: take all subsets of an n-element set and add a new element x. Every old subset either does or does not get x, so the count doubles.

The in/out choice is exactly a binary string. For A = {a, b, c}, write 1 if an element is in and 0 if it is out:

Bits (a b c) Subset
000 โˆ…
001
010
011 {b, c}
100
101 {a, c}
110 {a, b}
111 {a, b, c}

This lookup between subsets and binary numbers is used constantly in computer science (for example "bitmask" techniques).

Python Build the power set from bit patterns

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Subsets of a fixed size

How many subsets of an n-element set have exactly k elements? That number is the binomial coefficient C(n, k) ("n choose k"), equal to n! / (k! (n โˆ’ k)!). Adding up the counts for every size gives the total:

Text
C(n, 0) + C(n, 1) + ... + C(n, n) = 2โฟ

This is a neat identity with a set-theory proof: both sides count the subsets of an n-element set, the right side all at once and the left side sorted by size. For n = 4 the counts are 1, 4, 6, 4, 1, which sum to 16.

Python Counting subsets by size

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Power sets and subset relations

If A โІ B then P(A) โІ P(B): every subset of A is also a subset of B. Also, S โˆˆ P(A) means exactly the same as S โІ A. This translation between "element of the power set" and "subset" is worth memorizing.

When a question asks "Is an element of P(A)?", rewrite it as "Is โІ A?", which means "Is 1 โˆˆ A?". Peeling the layers one step at a time avoids most mistakes.

A glimpse of what comes next

The power set of a set always has strictly more elements than the set itself, and this stays true even for infinite sets. That fact, due to Cantor, shows there is no largest infinity. You will prove it in the chapter on cardinality.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many subsets does a set with 5 elements have?

    Each of 5 elements is either in or out: 2^5 = 32.
  2. 2. What is P(โˆ…)?

    The empty set has exactly one subset, itself, so P(โˆ…) = {โˆ…}, a set with one element.
  3. 3. Which statement is true for A = {1, 2}?

    {1} is a subset of A, so it is an element of P(A). The number 1 is an element of A, not of P(A).
  4. 4. How many 2-element subsets does a 5-element set have?

    C(5, 2) = 5! / (2! 3!) = 10.

Summary

  • P(A) is the set of all subsets of A; it always contains โˆ… and A.
  • If |A| = n then |P(A)| = 2โฟ: each element is in or out.
  • Subsets correspond to binary strings (bitmasks) of length n.
  • The number of k-element subsets is C(n, k), and these counts add up to 2โฟ.
  • S โˆˆ P(A) means the same as S โІ A.

Next: Special Sets and Intervals