Course contentsShow
← Computer Science
Lesson 61 of 2,8722. Discrete Mathematics for CSFree lesson

Power Sets

Define the power set as the set of all subsets; compute power sets and their cardinality for small sets.

Power Sets

What you'll learn: You'll discover how to create the power set—the collection of all possible subsets of a set—and calculate how many subsets any set contains.

What Is a Power Set?

The power set of a set is the set that contains every possible subset of the original set, including the empty set and the set itself.

Think of it like a recipe book analogy: if you have ingredients {flour, sugar, eggs}, the power set is like listing every possible combination you could choose—using all three, just two, just one, or none at all.

Computing Power Sets

Let's say we have a set A = {1, 2}.

The power set, written as P(A) or ℘(A), includes:

  • The empty set: ∅ or {}
  • Each single element: {1}, {2}
  • All elements together: {1, 2}

So P(A) = { ∅, {1}, {2}, {1, 2} }

Notice that the power set itself is a set containing other sets as elements.

Cardinality Formula

Here's a powerful shortcut: if a set has n elements, its power set has exactly 2ⁿ elements.

  • Set with 0 elements → 2⁰ = 1 subset (just ∅)
  • Set with 1 element → 2¹ = 2 subsets
  • Set with 2 elements → 2² = 4 subsets (as we saw above)
  • Set with 3 elements → 2³ = 8 subsets

Why powers of 2? For each element, you make a binary choice: include it or don't. With n elements, that's n independent yes/no decisions—just like counting in binary!

Example with Three Elements

For B = {a, b, c}:

P(B) = { ∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }

That's 8 subsets total, confirming 2³ = 8.

Key Takeaway: The power set contains all possible subsets of a set; if the original set has n elements, the power set has exactly 2ⁿ elements.