allsubsets

All subsets of a set S are collectively called the power set of S, denoted P(S) or 𝒫(S). A subset T satisfies T ⊆ S; the empty set ∅ is a subset of every set, and S itself is also a subset of S. The power set contains every possible combination of elements of S and thus has 2^|S| elements for a finite S with |S| = n.

Example: if S = {1, 2, 3}, its subsets are ∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, and {1,2,3}.

Generation and counting: For finite sets, all subsets can be enumerated by iterating binary masks from 0 to 2^n − 1, where each bit indicates the presence or absence of a corresponding element. Subsets of a fixed size k are called k-subsets or combinations, and there are C(n, k) of them.

Properties: The collection P(S), equipped with union, intersection, and complement (relative to a universal set), forms a Boolean algebra. The subset relation ⊆ provides a natural partial order, turning P(S) into a lattice with ∅ as the bottom element and S as the top.

Infinite case: If S is infinite, the power set 𝒫(S) has cardinality 2^|S|. By Cantor’s theorem, 2^|S| > |S|, and if S is countably infinite, 𝒫(S) is uncountable.

Applications: In probability theory, events are subsets of a sample space; in logic and computer science, subsets model properties and states; in combinatorics, power sets underpin various counting and optimization problems.