Power set (set of all subsets)

Definition and simple examples

Formally, P(S) = {X | X \u2286 S}. For a small finite example, if S = {a, b} then P(S) = {\u2205, {a}, {b}, {a, b}}. When S has n elements (n a nonnegative integer), the power set contains 2^n distinct subsets; this count arises because each element may either be included or excluded independently.

Properties

The power set has several important structural features. It is partially ordered by inclusion, and under union and intersection it forms a Boolean algebra. There is a natural correspondence between subsets of S and {0,1}-valued functions on S (characteristic functions), so P(S) is equinumerous with the set of all functions S \u2192 {0,1} when S is finite. A fundamental result, Cantor's theorem, states that there is no bijection between a set and its power set: P(S) always has strictly greater cardinality than S, even for infinite sets. Cardinality considerations drive many arguments in set theory and logic.

History and context

The notion of collecting all subsets is implicit in early work on sets and logic, and it became explicit with the formal development of set theory in the late 19th and early 20th centuries. Cantor's work on different sizes of infinity highlighted the importance of power sets and led to foundational questions about sets, functions and cardinalities. In category-theoretic language the power-set construction is an important example of a functor from the category of sets to itself. Finite set examples are standard in introductory texts.

Uses and notable facts

Power sets serve as the universe for many constructions: collections of events in probability are subsets of a sample space; topologies on a set are particular families of subsets and hence subcollections of a power set; in computer science, bit vectors represent subsets efficiently. The power set also underpins combinatorial counting, where selecting any subset corresponds to a choice counted by binomial coefficients. Because P(S) is so central, it also appears in proofs and counterexamples about functions, orders and algebraic structures. Examples

Related concepts

• Boolean algebra: P(S) with union, intersection and complement.
• Characteristic function: bijection between P(S) and {0,1}^S.
• Cantor's theorem: no set is the same size as its power set.