Power Sets

How many ways can you choose a committee from five people? This includes choosing nobody or everybody. This concrete counting question hides a deep set-theoretic idea. The collection of all subsets of a set is itself a set. It is worth studying in its own right. This article introduces the power set $\mathcal{P}(A)$ . This is the set of every subset of $A$ . It shows that its size relates to the size of $A$ . The relationship follows a strikingly clean formula. The power set operation is one of the most important set-forming tools in mathematics. It is the mechanism that lets us talk about "the set of all subsets." This in turn is the raw material for defining relations, functions, topologies, and probability spaces. (A relation on $A$ is a subset of $A \times A$ . Hence it is an element of $\mathcal{P}(A\times A)$ .) Wherever mathematics needs to quantify over "all possible collections of things drawn from $A$ ," it is quantifying over $\mathcal{P}(A)$ . The central quantitative fact of this article is this. For a finite set $A$ with $n$ elements, $\mathcal{P}(A)$ has exactly $2^n$ elements. We will prove this rigorously by induction, not just illustrate it. We will also see why the empty set and $A$ itself always belong to $\mathcal{P}(A)$ . We will explore how power sets interact with the The Algebra of Sets operations. We will also see why $\mathcal{P}(A)$ is never the same size as $A$ . This holds true even when $A$ is infinite. This is Cantor's theorem, previewed here in its finite form and stated in full. By the end, you will be able to construct $\mathcal{P}(A)$ for small sets by hand. You will be able to prove the $2^n$ formula from first principles. You will also see how the power set operation sets the stage for further work. It supports the formal construction of Ordered Pairs and the The ZFC Axioms Overview. There, "power set" is promoted to its own axiom. This happens precisely because it is not derivable from more primitive assumptions.

Key takeaways

$\mathcal{P}(A)$ is the set of all subsets of $A$ , including $\emptyset$ and $A$ itself.
Membership in $\mathcal{P}(A)$ and subset-hood of $A$ are the same relation viewed two ways: $x \in \mathcal{P}(A) \iff x \subseteq A$ .
For finite $A$ with $|A|=n$ , the size of the power set is $|\mathcal{P}(A)| = 2^n$ , proved by induction on $n$ .
$\mathcal{P}(\emptyset) = \{\emptyset\}$ , a one-element set — a classic source of confusion between $\emptyset$ and $\{\emptyset\}$ .
$\mathcal{P}(A)$ interacts predictably with $\cap$ but only partially with $\cup$ : $\mathcal{P}(A\cap B) = \mathcal{P}(A)\cap \mathcal{P}(B)$ , while $\mathcal{P}(A\cup B) \supseteq \mathcal{P}(A)\cup\mathcal{P}(B)$ generally with no equality.
Key idea: taking the power set converts "elements of $A$ " into "subsets of $A$ ," and doing so always strictly increases cardinality — even infinitely.

Where this lives today

The power set is the quiet workhorse behind enormous amounts of mathematics and computing. In logic and set theory, $\mathcal{P}(A)$ is needed to define relations and functions on $A$ (a function $A \to B$ is a special subset of $A \times B$ , hence an element of $\mathcal{P}(A\times B)$ ), and Cantor's theorem that $|\mathcal{P}(A)| > |A|$ shows there is no single "largest infinity," a cornerstone of modern foundations alongside the The ZFC Axioms Overview. In probability theory, when a sample space $\Omega$ is finite, the collection of all "events" is exactly $\mathcal{P}(\Omega)$ , so the $2^n$ formula literally counts how many distinct events are possible. In computer science, the power set of a finite alphabet's state set underlies the subset construction used to convert nondeterministic finite automata into deterministic ones, and boolean/bitmask representations of subsets (each subset of an $n$ -element set as an $n$ -bit integer) are a direct computational encoding of $\mathcal{P}(A) \cong \{0,1\}^n$ . In combinatorics, counting subsets by size recovers the binomial coefficients and Pascal's triangle. In topology, a topology on a set $X$ is by definition a distinguished sub-collection of $\mathcal{P}(X)$ satisfying closure axioms, so all of point-set topology is built as structured subsets of a power set.

Ask the tutor: How does the finite proof that $|\mathcal{P}(A)| = 2^n$ relate to Cantor's diagonal argument that $|A| < |\mathcal{P}(A)|$ for infinite sets?

A

Intuition

Think of $A$ as a bag of labeled marbles. A subset of $A$ is any sub-bag you can form by including or excluding each marble — you never invent new marbles, and you never duplicate one. The power set $\mathcal{P}(A)$ is the "bag of all possible sub-bags," where each sub-bag, including the empty sub-bag and the full bag, is treated as a single new object. The key mental shift is a change of level: elements of $A$ are marbles, but elements of $\mathcal{P}(A)$ are entire sub-bags. This is why $|\mathcal{P}(A)|$ can be so much larger than $|A|$ : for each of the $n$ marbles, an independent binary choice ("in" or "out") determines a subset, and independent binary choices multiply. Three marbles give $2\times2\times2 = 8$ sub-bags. This bijective correspondence between subsets and binary choice-sequences (or, equivalently, functions from $A$ to $\{0,1\}$ ) is exactly why the notation $2^A$ is used for $\mathcal{P}(A)$ : it literally counts functions from $A$ into a two-element set.

Figure

The power set of

A=\{a,b,c\}

arranged by subset size, forming the Boolean lattice

\mathcal{P}(A)

Central results

A

n

A, B

\subseteq

A, B

X \in \mathcal{P}(A) \cup \mathcal{P}(B)

Worked examples

Example 1 — a four-element set with mixed-type elements. Let $A = \{1, 2, \{1\}, \emptyset\}$ . Note this set has four distinct elements: the numbers $1$ and $2$ , the set $\{1\}$ (which is not the same object as the number $1$ ), and the empty set $\emptyset$ (which is not the same object as the number $2$ or anything else here). By the theorem, $|\mathcal{P}(A)| = 2^4 = 16$ . We list all 16 subsets systematically by size:

Size 0 (1 subset): $\emptyset$ .
Size 1 (4 subsets): $\{1\}$ , $\{2\}$ , $\{\{1\}\}$ , $\{\emptyset\}$ .
Size 2 (6 subsets): $\{1,2\}$ , $\{1,\{1\}\}$ , $\{1,\emptyset\}$ , $\{2,\{1\}\}$ , $\{2,\emptyset\}$ , $\{\{1\},\emptyset\}$ .
Size 3 (4 subsets): $\{1,2,\{1\}\}$ , $\{1,2,\emptyset\}$ , $\{1,\{1\},\emptyset\}$ , $\{2,\{1\},\emptyset\}$ .
Size 4 (1 subset): $\{1,2,\{1\},\emptyset\} = A$ .

Total: $1+4+6+4+1 = 16$ , matching $\binom{4}{0}+\binom{4}{1}+\binom{4}{2}+\binom{4}{3}+\binom{4}{4} = 2^4$ , an instance of the binomial theorem counting subsets by size — a fact consistent with, and giving an alternate proof strategy for, the theorem above. Note the subtlety: $\{1\} \in A$ as an element, and separately $\{1\}$ is also a subset of $A$ (since $1 \in A$ ), so $\{1\}$ appears both as a member of $A$ and as a member of $\mathcal{P}(A)$ — these are different logical roles for the same object, a common point of confusion.

Example 2 — nested power sets and their sizes. Let $A = \{\, \emptyset,\ \{\emptyset\}\,\}$ , so $|A| = 2$ (its two elements are $\emptyset$ and $\{\emptyset\}$ , which are distinct: $\emptyset$ has no elements, while $\{\emptyset\}$ has exactly one element, namely $\emptyset$ ). Then $|\mathcal{P}(A)| = 2^2 = 4$ , and explicitly

\mathcal{P}(A) = \big\{\, \emptyset,\ \{\emptyset\},\ \{\{\emptyset\}\},\ \{\emptyset,\{\emptyset\}\} \,\big\}.

Now compute the power set of this power set. Since $|\mathcal{P}(A)| = 4$ , the theorem gives

|\mathcal{P}(\mathcal{P}(A))| = 2^4 = 16.

This illustrates iterated power-set formation: starting from $|A|=2$ , we get sizes $2, 4, 16, 65536, \dots$ under repeated application of $\mathcal{P}$ , since $2^{(2^{(2^{(\cdots)})})}$ towers explosively. This is precisely the tower construction (with $A=\emptyset$ ) used to build the finite ordinals inside a model of the The ZFC Axioms Overview, where $\mathcal{P}$ is applied repeatedly starting from $\emptyset$ .

Counterexample

\mathcal{P}(A)\cup\mathcal{P}(B) = \mathcal{P}(A\cup B)

Scope, edge cases & common traps

Situation	What to watch for
$A = \emptyset$	$\mathcal{P}(\emptyset) = \{\emptyset\}$ , which has one element, not zero. Do not confuse $\emptyset$ with $\{\emptyset\}$ .
$A$ infinite	$\mathcal{P}(A)$ is still well-defined but $2^n$ has no meaning as ordinary exponentiation of naturals; cardinal exponentiation is used instead, and $\|\mathcal{P}(A)\| > \|A\|$ still holds (Cantor's theorem).
$x \in A$ vs. $\{x\} \subseteq A$	These express the same fact in different registers; $\{x\} \in \mathcal{P}(A) \iff x \in A$ . Do not write $x \in \mathcal{P}(A)$ unless $x$ is itself a subset of $A$ .
$A \in \mathcal{P}(A)$	Always true, since $A \subseteq A$ ; a frequent first-instinct error is to think $A$ is "too big" to be its own subset.
Counting by size	$\sum_{k=0}^n \binom{n}{k} = 2^n$ is consistent with, but is a different proof route from, the induction given here; both are valid and worth knowing.

The mathematician behind it

Origins · 1 minGeorg Cantor and how this was discovered

Georg Cantor

1845–1918 · Founder of set theory, University of Halle

Cantor developed the theory of sets and cardinal numbers in the 1870s–1890s, introducing the very idea of comparing the "sizes" of infinite collections. His 1891 diagonal argument, proving that no set can be put in bijection with its own power set, is the infinite generalization of the finite fact $|\mathcal{P}(A)| = 2^{|A|} > |A|$ proved here, and it revolutionized mathematics' understanding of infinity.

History

- 1874 — Cantor shows the real numbers cannot be put in bijection with the natural numbers, launching the study of different sizes of infinity.

- 1883 — Cantor introduces ordinal numbers and the transfinite iteration of set-forming operations, including repeated power-set formation.

- 1891 — Cantor publishes the diagonal argument, proving in full generality that

|A| < |\mathcal{P}(A)|

for every set

A

, finite or infinite.

- 1908 — Ernst Zermolo axiomatizes set theory, explicitly including a Power Set Axiom asserting that

\mathcal{P}(A)

exists as a set whenever

A

does.

- 1922 — Abraham Fraenkel and Thoralf Skolem refine Zermelo's axioms into the system now called ZFC, in which the power set axiom remains an independent, irreducible postulate.

A

itself an element of

\mathcal{P}(A)

Yes, always. By definition $\mathcal{P}(A) = \{X : X \subseteq A\}$ , and $A \subseteq A$ holds for every set $A$ (every element of $A$ is, trivially, an element of $A$ ). So $A \in \mathcal{P}(A)$ for every set $A$ , with no exceptions — including when $A = \emptyset$ , giving $\emptyset \in \mathcal{P}(\emptyset)$ . This sometimes feels strange at first because informally "subset" suggests "smaller," but $\subseteq$ permits equality; the strict subset relation $\subsetneq$ is what excludes $A$ from being counted as smaller than itself.

Why is

\mathcal{P}(\emptyset)

not just

\emptyset

$\mathcal{P}(\emptyset)$ is the set of all subsets of $\emptyset$ , and there is exactly one such subset: $\emptyset$ itself, since the only set with no elements not in $\emptyset$ is $\emptyset$ . So $\mathcal{P}(\emptyset) = \{\emptyset\}$ , a set containing one element, namely the empty set. This is different from $\emptyset$ , which contains zero elements. Confusing "the set containing the empty set" with "the empty set" is one of the most common early mistakes in set theory; checking cardinalities ( $|\{\emptyset\}| = 1 \ne 0 = |\emptyset|$ ) is the fastest way to catch the error.

Does the formula

|\mathcal{P}(A)| = 2^n

still make sense if

A

is infinite?

The formula as ordinary arithmetic ( $2^n$ for a natural number $n$ ) only applies when $A$ is finite. When $A$ is infinite, mathematicians use cardinal exponentiation, writing $|\mathcal{P}(A)| = 2^{|A|}$ as a definition of cardinal exponentiation rather than a computation, and Cantor's theorem guarantees $2^{|A|} > |A|$ regardless. So the symbol $2^{|A|}$ generalizes, but the proof method here (finite induction) does not directly transfer; the infinite case needs Cantor's diagonal argument instead.

How does the power set relate to binary strings or bitmasks?

There is a natural bijection between $\mathcal{P}(A)$ and the set of functions $A \to \{0,1\}$ : given $X \subseteq A$ , define its indicator function sending $a \mapsto 1$ if $a \in X$ and $a \mapsto 0$ otherwise. When $A = \{a_1,\dots,a_n\}$ is finite, such a function is just an $n$ -bit string, and there are exactly $2^n$ of them — this is the combinatorial heart of why $|\mathcal{P}(A)| = 2^n$ , and it is also literally how computers represent subsets of a small finite set as integers (bitmasks) for fast set operations.

\mathcal{P}(A) \cup \mathcal{P}(B)

ever equal to

\mathcal{P}(A \cup B)

Yes, exactly when $A \subseteq B$ or $B \subseteq A$ . If, say, $A \subseteq B$ , then $A \cup B = B$ , so $\mathcal{P}(A\cup B) = \mathcal{P}(B)$ ; and since $A \subseteq B$ implies $\mathcal{P}(A) \subseteq \mathcal{P}(B)$ (any subset of $A$ is a subset of $B$ too), we get $\mathcal{P}(A) \cup \mathcal{P}(B) = \mathcal{P}(B)$ as well, giving equality. Without such an inclusion between $A$ and $B$ , as the counterexample shows, equality fails because "mixed" subsets drawing from both sets appear only on the right-hand side.

Why does set theory need a special axiom just to guarantee power sets exist?

Within the axiomatic system ZFC, most set-existence facts (pairing, union, subsets satisfying a property) are derivable from a handful of basic axioms, but the existence of $\mathcal{P}(A)$ as a set, for arbitrary infinite $A$ , cannot be proved from the other standard axioms — it must be postulated separately as the Power Set Axiom. This is because $\mathcal{P}(A)$ can be enormously larger than $A$ (Cantor's theorem), and no combination of pairing, union, and separation alone can produce an object of that much greater size; a genuinely new axiom is required.

Can I compute

|\mathcal{P}(A)|

without listing every subset?

Yes — that is the point of the theorem. If $|A| = n$ is known, then $|\mathcal{P}(A)| = 2^n$ immediately, with no need to enumerate. The induction proof above shows why the doubling happens at each step (split subsets into those avoiding a fixed element and those containing it, and each half is in bijection with $\mathcal{P}$ of the smaller set), which is more illuminating than direct listing and generalizes cleanly to the counting-by-size and bit-string viewpoints mentioned in the worked examples.