Given a set A, the power set \mathcal{P}(A) is the set of every subset of A. If A has three elements, a little bookkeeping shows that \mathcal{P}(A) has eight elements. That eight is not arbitrary — it is 2^3, and the exponent 3 is the number of elements in A. The formula |\mathcal{P}(A)| = 2^{|A|} is one of the cleanest counting facts in elementary mathematics, and the clearest way to see why is to walk a tree of decisions: for each element of A, you decide "include it" or "leave it out," and every distinct combination of those decisions is a distinct subset.

The setup

Let A = \{a, b, c\}. The subsets of A are all the sets you can form by picking some or none of the elements a, b, c. The smallest subset is \varnothing (pick none); the largest is \{a, b, c\} itself (pick all). Between those extremes live the singletons and the pairs.

To list them systematically — without missing any or repeating any — we build a tree. At each level, one element of A is under consideration. The tree has two branches at each level: include this element (left) or exclude it (right). After three levels (a, then b, then c), each leaf of the tree corresponds to one unique subset.

A binary decision tree showing the 8 subsets of a three element set A horizontal binary tree with three decision levels. At the root is the empty set. The first level asks include a or exclude a, branching into two nodes. The second level asks the same question for b, and the third level for c. After three levels the tree has eight leaves, each labelled with the subset formed by the choices made: the eight subsets are empty set, curly c, curly b, curly b c, curly a, curly a c, curly a b, and curly a b c. Beside the tree a label reads total subsets equals two to the power three equals eight. start ∅ +a −a +b −b +b −b {a, b, c} {a, b} {a, c} {a} {b, c} {b} {c} ∅ |P(A)| = 2³ = 8 one leaf per subset
The decision tree for finding all subsets of $A = \{a, b, c\}$. At each level you choose include (+) or exclude (−) one element. Three levels of binary choices gives $2 \times 2 \times 2 = 8$ leaves, and each leaf is a distinct subset of $A$. The order of the leaves from top to bottom lists the power set: $\{a, b, c\}$, $\{a, b\}$, $\{a, c\}$, $\{a\}$, $\{b, c\}$, $\{b\}$, $\{c\}$, $\varnothing$.

The count: why 2³

At each of the three levels, you have exactly two independent choices: include or exclude. The total number of distinct paths from root to leaf is the product of the choices at each level — 2 \times 2 \times 2 = 8. In general, if |A| = n, the tree has n levels and 2^n leaves, so |\mathcal{P}(A)| = 2^n.

Why "independent": whether you include a does not constrain whether you include b or c. Each element is its own separate yes/no decision, and the decisions multiply. This is exactly the same counting principle you use to count the outcomes of n coin flips — 2^n outcomes, because each flip is independent and has 2 options.

The eight subsets, listed out

Reading the tree leaves from top to bottom:

  1. \{a, b, c\} — include all three. The full set.
  2. \{a, b\} — include a and b, exclude c.
  3. \{a, c\} — include a and c, exclude b.
  4. \{a\} — include only a. A singleton.
  5. \{b, c\} — exclude a, include b and c.
  6. \{b\} — include only b. A singleton.
  7. \{c\} — include only c. A singleton.
  8. \varnothing — exclude all three. The empty subset.

Count: 1 subset of size 3, 3 of size 2, 3 of size 1, 1 of size 0. Total 1 + 3 + 3 + 1 = 8. Those counts are the entries of row 3 of Pascal's triangle, which is not an accident — the number of k-element subsets of an n-element set is the binomial coefficient \binom{n}{k}, and the sum \sum_k \binom{n}{k} = 2^n is an identity you will meet again in the chapter on combinations.

A compact equivalence: binary strings

Each path through the tree can be encoded as a string of three bits, where 1 means "include" and 0 means "exclude." The bits correspond to a, b, c in order.

The eight binary strings of length 3 are exactly 0 through 7 in binary — the numbers 0, 1, 2, 3, 4, 5, 6, 7. Each one encodes a unique subset. This is the cleanest possible bijection between the power set and a set of numbers, and it is why programmers speak of a "bitmask" when they want to represent a subset: each bit is the answer to "is this element included?"

The pattern for larger sets

The counting argument extends perfectly:

Power sets grow very fast. A 20-element set already has more subsets than the population of many small towns. By |A| = 30, the power set is bigger than a billion. The exponential explosion you saw for doubling in Exponents and Powers is exactly the same growth happening here.

One thing that often surprises beginners

The power set always contains \varnothing and A itself. Those two are automatic — every set is a subset of itself, and the empty set is a subset of every set. So |\mathcal{P}(A)| \geq 2 for any set A (even one with a single element). A 1-element set A = \{a\} has power set \mathcal{P}(A) = \{\varnothing, \{a\}\}, which has cardinality 2 = 2^1. A 0-element set (the empty set itself) has power set \mathcal{P}(\varnothing) = \{\varnothing\}, which has cardinality 1 = 2^0. The formula 2^n works for n = 0 too, and recovers the single subset correctly.

The reflex

To find the power set of a finite set A: walk the tree. At each element, ask "include or exclude?" The distinct answer paths are the distinct subsets, and there are 2^{|A|} of them. No guessing, no missing any, no listing the same subset twice. The tree is the proof and the construction at once.

Related: Sets — Introduction · The Box Model of a Set · Cardinality Meter · Exponents and Powers