Power set
The set of all subsets of a given set.
In mathematics, the power set of a set S is the collection of every possible subset of S, including both the empty set and S itself. Under the ZFC axioms of set theory, the existence of this power set for any given set is guaranteed by a specific axiom, known as the axiom of power set. This concept is denoted by several notations: P(S), 𝒫(S), P(S), ℙ(S), or 2^S. Any subset of the power set is referred to as a family of sets over S.
For example, if S contains the elements {x, y, z}, its subsets are the empty set, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, and {x, y, z}. The power set of S is therefore the set containing all eight of these subsets.
If S is finite and has n elements (its cardinality is n), then the power set contains exactly 2^n subsets. This explains the notation 2^S, which also arises from the idea of indicator functions. An indicator function for a subset A of S maps each element of S to either 1 (if the element is in A) or 0 (if it is not). The set of all such functions from S to {0, 1} is denoted {0, 1}^S, and it is equivalent—or bijective—to the power set. Since each element of S can be assigned one of two values, the total number of these functions is 2^n. Because the number 2 can itself be defined as the set {0, 1} (as in von Neumann ordinals), the power set is written as 2^S, and |2^S| = 2^|S|.
Cantor’s diagonal argument demonstrates that the power set of any set—whether finite or infinite—always has a strictly larger cardinality than the set itself. For instance, the power set of a countably infinite set is uncountably infinite. Moreover, the power set of the natural numbers can be placed in a one-to-one correspondence with the real numbers.
When equipped with the operations of union, intersection, and complement, the power set of S forms a σ-algebra over S and serves as a classic example of a Boolean algebra. Every finite Boolean algebra is isomorphic to the Boolean algebra of the power set of some finite set, though this does not hold for infinite Boolean algebras. However, any infinite Boolean algebra can be represented as a subalgebra of a power set Boolean algebra, as shown by Stone’s representation theorem.
Under the operation of symmetric difference, the power set of S forms an abelian group, with the empty set as the identity and each set as its own inverse. Under intersection, it forms a commutative monoid, with S itself as
- definition
- Set of all subsets of a set S
- notation
- P(S), 𝒫(S), P(S), 2^S
- cardinality (finite)
- |P(S)| = 2^n, where n = |S|
- key theorem
- Cantor's diagonal argument shows power set has strictly higher cardinality than the original set
- algebraic structure
- Forms a Boolean algebra, an abelian group under symmetric difference, and a commutative monoid under intersection
- example
- For S = {x, y, z}, P(S) has 8 subsets
Lore & Background
The power set of a set S is the collection of every possible subset, from the empty set to S itself. For a finite set with n elements, the power set contains exactly 2^n subsets, a fact that motivates the notation 2^S. This relationship is demonstrated through indicator functions: each subset corresponds to a function from S to {0,1}, and the set of all such functions, denoted {0,1}^S, is bijective to the power set. Cantor's diagonal argument shows that the power set of any set always has a strictly larger cardinality than the set itself, so the power set of a countably infinite set is uncountably infinite.
Reader's Guide
The power set is a central object in set theory and mathematics. Its existence is guaranteed by the axiom of power set in ZFC set theory. The power set of a set S, together with union, intersection, and complement, forms a σ-algebra and is the prototypical example of a Boolean algebra; any finite Boolean algebra is isomorphic to the power set of a finite set. The power set also forms an abelian group under symmetric difference and a commutative monoid under intersection, and together these operations yield a Boolean ring. The notation 2^S reflects the bijection between the power set and the set of all functions from S to {0,1}, and the cardinality identity |2^S| = 2^|S| holds. The binomial theorem relates to the power set: the number of k-element subsets of an n-element set is the binomial coefficient C(n,k), and summing over k gives 2^n. The power set can be defined recursively: for the empty set, P({}) = {{}}; for a non-empty set S with element e and T = S \ {e}, P(S) = P(T) ∪ {t ∪ {e} : t ∈ P(T)}. Subsets of limited cardinality are denoted P_κ(S) or [S]^κ.
Did You Know?
- The power set of a set with n elements has exactly 2^n subsets.
- Cantor's diagonal argument shows the power set of any set has strictly greater cardinality than the set itself.
- The power set of a set S forms a Boolean algebra and a Boolean ring under union, intersection, and symmetric difference.
- The notation 2^S for the power set comes from the bijection with the set of all functions from S to {0,1}.
More in Sets And Logic 25-32
Elsewhere in the Sets And Logic universe
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record