Power Set Calculator
Our free algebra calculator solves power set problems. Get worked examples, visual aids, and downloadable results. Get results you can export or share.
Formula
|P(S)| = 2^n where n = |S|
The power set P(S) of a set S with n elements contains all 2^n possible subsets, from the empty set to S itself. The number of subsets of size k is C(n,k) = n!/(k!(n-k)!).
Worked Examples
Example 1: Power Set of a 3-Element Set
Problem: Find the power set of S = {1, 2, 3}.
Solution: Set S has 3 elements, so |P(S)| = 2^3 = 8 subsets.\nSubsets by cardinality:\n Size 0: { } (1 subset)\n Size 1: {1}, {2}, {3} (3 subsets)\n Size 2: {1,2}, {1,3}, {2,3} (3 subsets)\n Size 3: {1,2,3} (1 subset)\nTotal: C(3,0) + C(3,1) + C(3,2) + C(3,3) = 1 + 3 + 3 + 1 = 8\nProper subsets: 8 - 1 = 7
Result: Power set has 8 subsets | 7 proper subsets | 7 non-empty subsets
Example 2: Power Set of a 4-Element Set
Problem: Find the power set of S = {x, y, z, w} and count subsets by size.
Solution: Set S has 4 elements, so |P(S)| = 2^4 = 16 subsets.\nSubsets by cardinality:\n Size 0: C(4,0) = 1 subset (empty set)\n Size 1: C(4,1) = 4 subsets\n Size 2: C(4,2) = 6 subsets\n Size 3: C(4,3) = 4 subsets\n Size 4: C(4,4) = 1 subset\nTotal = 1 + 4 + 6 + 4 + 1 = 16\nProper subsets: 16 - 1 = 15
Result: Power set has 16 subsets | 15 proper subsets | Largest group: 6 subsets of size 2
Frequently Asked Questions
What is a power set in set theory?
A power set is the set of all possible subsets of a given set, including the empty set and the set itself. If S is a set with n elements, the power set P(S) contains exactly 2^n subsets. For example, if S = {a, b}, then P(S) = { {}, {a}, {b}, {a, b} }, which has 2^2 = 4 elements. The power set is a fundamental concept in set theory, combinatorics, and mathematical logic. It demonstrates how the number of subsets grows exponentially with the size of the original set, which has important implications for computational complexity.
Why does a set with n elements always have exactly 2^n subsets?
The reason is that each element has exactly two choices: either it is included in a subset or it is not. Since each of the n elements independently makes this binary choice, the total number of possible combinations is 2 multiplied by itself n times, which equals 2^n. This can also be understood through the binary representation: each subset corresponds to a unique n-bit binary number where a 1 in position k means element k is included and a 0 means it is excluded. Since there are exactly 2^n different n-bit binary numbers (from 0 to 2^n - 1), there are exactly 2^n subsets.
How is the power set used in probability theory?
In probability theory, the power set of a sample space forms the largest possible sigma-algebra (or event space) for defining probabilities. Each element of the power set represents a possible event, and a probability function assigns a value between 0 and 1 to each event. For a finite sample space with n outcomes, the power set provides all 2^n possible events that could be assigned probabilities. For infinite sample spaces, the full power set may be too large to work with, leading to the use of smaller sigma-algebras. The concept of power sets also underlies the axioms of probability established by Kolmogorov.
Can the power set of an infinite set be computed?
The power set of an infinite set exists mathematically but cannot be fully enumerated or computed. Cantor proved that the power set of any set, finite or infinite, always has strictly greater cardinality than the original set. For instance, the natural numbers have cardinality aleph-null, but the power set of the natural numbers has cardinality 2^(aleph-null), which equals the cardinality of the continuum (the real numbers). This result is called Cantor theorem and is proved by a diagonalization argument. The continuum hypothesis, one of the most famous unsolved problems, asks whether there is a cardinality strictly between aleph-null and the continuum.
What is the computational complexity of generating a power set?
Generating a complete power set has exponential time and space complexity of O(2^n), where n is the number of elements. This means the computation doubles with each additional element. A set of 10 elements produces 1,024 subsets, 20 elements produces over one million subsets, and 30 elements produces over one billion subsets. Due to this exponential growth, generating complete power sets becomes impractical for sets larger than about 20-25 elements on standard hardware. Algorithms for power set generation include iterative bitmask enumeration, recursive approaches, and Gray code ordering which changes only one element between consecutive subsets.
How do power sets relate to Boolean algebra and logic?
The power set of any set forms a Boolean algebra under the operations of union (OR), intersection (AND), and complement (NOT). This Boolean algebra is isomorphic to the algebra of n-bit binary strings with bitwise operations. Each subset corresponds to a truth assignment for n Boolean variables. The lattice structure of the power set, ordered by inclusion, mirrors the logical implication relationships between conjunctions of literals. This connection is fundamental in digital circuit design, database query optimization, and formal verification of software systems.