Union and intersection combine sets while staying "at the same level". There are, however, two constructions that produce new and much larger sets: the power set, which collects all subsets, and the Cartesian product, which forms all possible pairs. They underlie concepts such as relations, functions and configuration spaces, and they explain why certain problems grow so quickly.
The power set
The power set of A, written 𝒫(A) or 2ᴬ, is the set of all subsets of A, including the empty set and A itself.
If A = {r, w, x}:
𝒫(A) = {∅, {r}, {w}, {x}, {r, w}, {r, x}, {w, x}, {r, w, x}}
There are 8 elements. In general, if |A| = n, then |𝒫(A)| = 2ⁿ.
Why 2ⁿ
Building a subset means making, for each element of A, a binary decision: in or out. There are n independent decisions, so the combinations number 2 · 2 · … · 2 = 2ⁿ.
This reasoning also suggests a very practical representation: a subset of an n-element set can be encoded as a string of n bits. With the order r, w, x, the string 101 represents {r, x} and 000 the empty set. That is exactly how Unix permissions are stored: read, write and execute are three bits, and permission 5 in octal, 101 in binary, means "read and execute".
Enumerating all subsets
The correspondence with binary numbers gives an algorithm straight away:
def power_set(elements):
n = len(elements)
for mask in range(2 ** n):
yield {elements[i] for i in range(n) if mask >> i & 1}
list(power_set(["r", "w", "x"]))
The loop counts from 0 to 2ⁿ − 1 and, for each number, includes the elements whose bits are set. It works well while n is small: with 30 elements there are more than a billion subsets. That is why algorithms that try "every combination" quickly become impractical.
The Cartesian product
The Cartesian product of A and B is the set of all ordered pairs (a, b) with a ∈ A and b ∈ B:
A × B = {(a, b) | a ∈ A, b ∈ B}
In an ordered pair the order matters: (1, 2) ≠ (2, 1). And, unlike sets, repetition is allowed: (3, 3) is a valid pair.
If A = {S, M, L} (sizes) and B = {black, white} (colours):
A × B = {(S, black), (S, white), (M, black), (M, white), (L, black), (L, white)}
There are 3 · 2 = 6 pairs. In general |A × B| = |A| · |B|.
More than two factors
The product extends to n sets, producing n-tuples: A₁ × A₂ × … × Aₙ. A row in a three-column database table is an element of D₁ × D₂ × D₃, where Dᵢ is the domain of values of each column. The Cartesian plane is ℝ × ℝ, and an IPv4 address is an element of {0, …, 255}⁴, a set with 256⁴ = 2³² elements.
The Cartesian product in SQL
A CROSS JOIN between two tables produces exactly the Cartesian product of their rows. With tables of 1,000 and 2,000 rows you get 2 million rows. A JOIN written without its linking condition has the same effect, and it is a classic mistake that makes query execution times explode.
Cartesian products and testing
When software has several configuration parameters, the space of all configurations is their Cartesian product. With a choice of 3 operating systems, 4 browsers and 5 languages, there are 3 · 4 · 5 = 60 combinations.
Testing them all is feasible; with ten parameters of five values each it no longer is (5¹⁰ is almost ten million). That is why techniques such as pairwise testing are used: you choose a subset of the Cartesian product in which every pair of values of different parameters appears at least once. Many defects depend on the interaction of just two parameters, and this approach catches them with far fewer tests.
Power set and product compared
| Power set | Cartesian product | |
|---|---|---|
| Elements | subsets of A | pairs (a, b) |
| Cardinality | 2ⁿ | n · m |
| Growth | exponential | polynomial |
| Example | permission combinations | product variants |
There is also a deep link: a relation between A and B is defined as a subset of A × B, that is, an element of 𝒫(A × B). The possible relations between two 3-element sets therefore number 2⁹ = 512.
In short
- The power set contains every subset and, if |A| = n, has 2ⁿ elements.
- Each subset can be encoded with n bits, like Unix permissions.
- The Cartesian product contains every ordered pair and has |A| · |B| elements.
- A CROSS JOIN, or a JOIN without a condition, produces the Cartesian product of the rows.
- A relation is a subset of the Cartesian product.
