Key takeaways
- The power set P(A) is the set of all subsets of A, including the empty set and A itself.
- A set with n elements has 2ⁿ subsets, because each element is independently either in or out of a subset.
- Subsets of {a₁, …, aₙ} correspond one-to-one with n-bit binary strings, which is how programs list them.
- The number of subsets with exactly k elements is C(n, k), and adding these over k gives 2ⁿ.
- P(∅) = {∅} has one element, and a power set is always strictly larger than the original set, even for infinite sets.
The power set of a set A, written P(A) or 2^A, is the set of all subsets of A. That is essentially Applied Discrete Structures' definition, and it is short enough to hide two things worth noticing: the elements of a power set are themselves sets, and every power set includes both the empty set and A itself.
MathWorld adds the fact this article is about: a set with n elements has a power set with 2ⁿ elements.
Listing a power set without missing anything
For A = {a, b, c}, organise the subsets by size:
| Size | Subsets | Count |
|---|---|---|
| 0 | ∅ | 1 |
| 1 | {a}, {b}, {c} | 3 |
| 2 | {a, b}, {a, c}, {b, c} | 3 |
| 3 | {a, b, c} | 1 |
| Total | 8 |
So P({a, b, c}) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}, with 8 = 2³ elements.
Listing by size is the safest hand method, because you can check each row's count independently. The counts 1, 3, 3, 1 are a row of Pascal's triangle, which is not a coincidence.
Three proofs that |P(A)| = 2ⁿ
Each proof shows a different way of thinking, and each is worth knowing.
1. The choice argument. To build a subset of {a₁, …, aₙ}, go through the elements one by one and decide: in or out? Each decision has two options and the decisions are independent, so by the multiplication principle there are 2 × 2 × ⋯ × 2 = 2ⁿ ways to decide. Different decisions give different subsets, and every subset arises from some sequence of decisions. So there are exactly 2ⁿ subsets.
2. The binary string argument. Write each subset as an n-bit string, with a 1 in position i if aᵢ is in the subset and 0 if not. For {a, b, c}:
| Subset | String |
|---|---|
| ∅ | 000 |
| {c} | 001 |
| {b} | 010 |
| {b, c} | 011 |
| {a} | 100 |
| {a, c} | 101 |
| {a, b} | 110 |
| {a, b, c} | 111 |
This is a one-to-one correspondence between subsets and n-bit strings, and there are 2ⁿ such strings, the numbers from 0 to 2ⁿ − 1 written in binary. It also gives a program a simple way to list every subset: loop a counter from 0 to 2ⁿ − 1 and read its bits as a "bitmask". The number bases guide covers binary if it is unfamiliar.
3. The induction argument. A set with 0 elements has one subset, ∅, and 2⁰ = 1. Suppose every set with k elements has 2ᵏ subsets, and add a new element x to get a set with k + 1 elements. Each of its subsets either leaves x out, giving one of the 2ᵏ old subsets, or includes x, giving an old subset with x added, another 2ᵏ. Total: 2ᵏ + 2ᵏ = 2ᵏ⁺¹. The step-by-step induction guide explains the format.
Subsets of a given size
The number of subsets of an n-element set that have exactly k elements is the binomial coefficient C(n, k), read "n choose k". Levin's Discrete Mathematics: An Open Introduction introduces binomial coefficients this way, as counts of subsets, and connects them to bit strings with a fixed number of 1s.
Since every subset has some size from 0 to n,
C(n, 0) + C(n, 1) + ⋯ + C(n, n) = 2ⁿ.
For n = 3: 1 + 3 + 3 + 1 = 8. This identity is a row sum of Pascal's triangle, and the binomial theorem guide proves it a third way, by setting x = y = 1 in (x + y)ⁿ.
The empty set traps
The empty set is where this topic is easiest to slip.
- P(∅) = {∅}. The empty set has one subset, itself. So its power set has one element, matching 2⁰ = 1. It is not empty.
- P({∅}) = {∅, {∅}}. The set {∅} has one element (the empty set), so its power set has 2¹ = 2 elements: the empty subset and the whole set.
- ∅ ∈ P(A) and ∅ ⊆ P(A) are both true, for any A. The first because ∅ is a subset of A; the second because ∅ is a subset of every set.
- A ∈ P(A), but A ⊆ P(A) is usually false. The elements of A are not, in general, subsets of A.
When in doubt, ask whether an expression is an element or a set of elements, and check membership against the definition. The set operations guide covers the ∈ versus ⊆ distinction in more detail.
Power sets are always bigger
For finite sets, 2ⁿ > n, so a power set always has more elements than the set it came from. Cantor's theorem says the same holds for infinite sets: there is no function from A onto P(A). The proof is a diagonal argument, and it means P(ℕ), the set of all sets of natural numbers, is uncountable, while ℕ is countable. MathWorld states the general version simply: power sets are larger than the sets associated with them. Countable versus uncountable sets explains what "larger" means for infinite sets.
Subset-counting exercises
- List P({1, 2}) and P({1, {2}}). How many elements does each have?
- How many subsets of {1, 2, …, 10} contain the number 1? (Half of them: 2⁹ = 512.)
- How many subsets of a 6-element set have exactly 2 elements? (C(6, 2) = 15.)
- Is {∅} ∈ P(P(∅))? (Yes: P(P(∅)) = {∅, {∅}}.)
Discrete Math: Study & Quiz has a unit on sets, functions and countability, with lessons and knowledge checks. Browse our education and brain-training apps, or continue through the discrete math hub.
Good to know
Frequently asked questions
What is the power set of {a, b, c}?
Why does a set with n elements have 2ⁿ subsets?
What is the power set of the empty set?
How many proper subsets does a set with n elements have?
Sources
- Cartesian Products and Power Sets (Applied Discrete Structures) (opens in a new tab)discretemath.org — accessed
- Power Set (opens in a new tab)Wolfram MathWorld — accessed
- Binomial Coefficients (Discrete Mathematics: An Open Introduction, 3rd edition, Oscar Levin) (opens in a new tab)Open Math Books — accessed
- 1.2 Subsets (Contemporary Mathematics) (opens in a new tab)OpenStax — accessed
About the author
Reign Creative LLC — The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.
We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.
No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.
Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.