Subsets and the Power Set
One set can live inside another. If every element of B is also an element
of A, we say B is a subset of
A, written B \subseteq A. If in addition
B is not the whole of A, it is a
proper subset, B \subset A. Two subsets always come free:
the empty set \varnothing \subseteq A (it has no elements
to check), and A \subseteq A itself.
Now ask a bigger question: what are all the subsets of a set, gathered together? That
collection is the power set \mathcal{P}(A) (also written
2^{A}) — a set whose elements are themselves sets.
Every element is in or out
Take A = \{a, b\}. Its subsets are:
\mathcal{P}(\{a,b\}) = \big\{\, \varnothing,\ \{a\},\ \{b\},\ \{a,b\} \,\big\}.
Four of them — and 4 = 2^2. That's no accident. To build a subset you
walk down the list of elements and make one yes/no choice for each: is it in, or
out? With n elements that's n independent binary
choices, so:
- A set with n elements has exactly
2^{n} subsets.
- Equivalently, |\mathcal{P}(A)| = 2^{|A|} — which is why the power
set is written 2^{A}.
- The empty set and the whole set are always among them.
The code below builds the power set by exactly that "in-or-out" idea: each number from
0 to 2^n - 1 is a pattern of bits saying which
elements to include. Press Run:
function powerSet<T>(items: T[]): T[][] {
const result: T[][] = [];
// Each mask from 0 to 2^n - 1 is one subset: bit i set = include items[i].
for (let mask = 0; mask < (1 << items.length); mask++) {
const subset: T[] = [];
for (let i = 0; i < items.length; i++) {
if (mask & (1 << i)) subset.push(items[i]);
}
result.push(subset);
}
return result;
}
const A = ["a", "b", "c"];
const P = powerSet(A);
console.log("number of subsets:", P.length, "= 2^" + A.length);
for (const s of P) console.log("{ " + s.join(", ") + " }");
Eight subsets for three elements, and the very first one printed is the empty set
\{\ \}. The power set grows explosively:
|A| = 10 already gives 1024 subsets.
Why the power set matters
The power set is the natural home of "all possible selections", so it shows up everywhere: the
events of a probability space are subsets of the sample space; a σ-algebra is a well-behaved
sub-collection of a power set. And it hides a deep surprise — the power set is always strictly
bigger than the set it came from, even for infinite sets, which is
Cantor's theorem and the
engine behind different sizes of infinity.
Yes — and the cleanest way to see it is to try to fail. For
\varnothing \subseteq A to be false, you'd need an element of
\varnothing that is not in A. But
\varnothing has no elements at all, so there is nothing to serve as a
counterexample. The condition is vacuously satisfied. This is also why the power
set of \varnothing is not empty: \mathcal{P}(\varnothing) =
\{\varnothing\}, a set with one element — and 2^0 = 1. ✓
-
Element vs subset. For A = \{1, 2\},
1 \in A but 1 \not\subseteq A (it isn't a
set), while \{1\} \subseteq A but \{1\} \notin A.
"Is a member of" (\in) and "is a subset of"
(\subseteq) are different relations.
-
\varnothing and \{\varnothing\} are
not the same: the first is empty; the second is a set containing one thing (the
empty set), so |\{\varnothing\}| = 1.