Power Set Calculator

What Is a Power Set?

In set theory and discrete mathematics, the power set of any set $S$, denoted as $\mathcal{P}(S)$ or $2^S$, is the set containing all possible subsets of $S$. Crucially, this collection includes the empty set $\emptyset$ (the subset with zero elements) and the original set $S$ itself.

For instance, consider the three-element set $S = \{1, 2, 3\}$. Its power set contains eight distinct subsets:

$$\mathcal{P}(S) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}$$

The Cardinality Formula: Why $2^n$?

If a finite set $S$ has cardinality $|S| = n$, then the cardinality of its power set is given by:

$$|\mathcal{P}(S)| = 2^n$$

This exponential relationship arises because when constructing any subset, each of the $n$ distinct elements in $S$ faces a binary choice: either it is included in the subset, or it is excluded. Since there are 2 independent possibilities for each element, the total number of combinations is:

$$\underbrace{2 \times 2 \times \dots \times 2}_{n \text{ times}} = 2^n$$

Subsets by Size and the Binomial Theorem

The subsets in a power set can be grouped according to their cardinality $k$, where $0 \le k \le n$. The count of subsets of size $k$ is given by the combination formula (binomial coefficient):

$$\binom{n}{k} = \frac{n!}{k!(n - k)!}$$

Summing over all possible subset sizes reproduces the total count via the Binomial Theorem:

$$\sum_{k=0}^{n} \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n} = (1 + 1)^n = 2^n$$

Proper Subsets and Non-Empty Subsets

Two common variations in mathematical problems are proper subsets and non-empty subsets:

• Proper Subsets: Any subset of $S$ that is strictly not equal to $S$ itself. Since only $S$ is excluded, there are $2^n - 1$ proper subsets.
• Non-Empty Subsets: Any subset containing at least one element. Excluding only the empty set $\emptyset$, there are $2^n - 1$ non-empty subsets.
• Non-Empty Proper Subsets: Excluding both $\emptyset$ and $S$ yields $2^n - 2$ subsets (for $n \ge 1$).

Generating Subsets with Binary Bitmasks

In computer science, power sets are often generated using binary bitmasks. An integer from $0$ to $2^n - 1$ represents a unique subset. If the $i$-th bit of the integer is set to 1, element $S[i]$ is included in the subset.

For example, with $S = \{a, b, c\}$:

• $0 = 000_2 \to \emptyset$
• $1 = 001_2 \to \{a\}$
• $2 = 010_2 \to \{b\}$
• $3 = 011_2 \to \{a, b\}$
• $7 = 111_2 \to \{a, b, c\}$

Explore related mathematical utilities including our Power of 2 Calculator and the Combinations Permutations Calculator.