2.2 Power Sets, Cartesian Products, and Cardinality: How Sets Construct New Spaces

A service offers three permissions: read, write, and delete. The permission set has three elements, while its possible selections number eight. Sets can filter existing objects and construct spaces of subsets, pairs, and mappings.

Power Set: The Set of All Subsets

The power set of a set A is denoted by:

𝒫(A) = {B | B ⊆ A}

If:

A = {read, write}

Then:

𝒫(A) = {
  ∅,
  {read},
  {write},
  {read, write}
}

Note the distinction in hierarchy:

read ∈ A
{read} ∈ 𝒫(A)
{read} ⊆ A

But read is typically not an element of 𝒫(A), because the elements of a power set are themselves sets.

Why n Elements Have 2ⁿ Subsets

When constructing subsets, each element has only two independent choices: include it or exclude it. For n elements, this results in:

2 × 2 × ... × 2 = 2ⁿ

Each subset can also be encoded as a binary vector of length n, representing permissions:

Permission order: [read, write, delete]

000 → ∅
001 → {delete}
010 → {write}
011 → {write, delete}
...
111 → {read, write, delete}

This explains why 30 independently defined boolean properties yield over a billion possible combinations. Exhaustive testing is often impractical at that size. Use constraints, coverage criteria, or generative methods to reduce the search space.

This Python 3 standard-library example fixes permission order and uses frozenset so that subsets can themselves be set elements:

from itertools import product

def power_set(items):
    items = tuple(items)
    if len(set(items)) != len(items):
        raise ValueError("input must list each element exactly once")
    return [frozenset(item for item, bit in zip(items, bits) if bit)
            for bits in product([0, 1], repeat=len(items))]

permissions = ("read", "write", "delete")
subsets = power_set(permissions)
print(len(subsets), sorted(subsets[1]))  # 8 ['delete']
print(power_set([]))                    # [frozenset()]
assert len(set(subsets)) == 2 ** len(permissions)

The empty set has one subset, itself, so 2⁰=1. No permission kinds still permits the empty selection. Duplicate inputs are rejected because [read, read] would let four bit patterns repeat the same subsets. This example materializes every subset and is intended for small checks.

Characteristic Functions Map Subsets to Boolean Functions

Given B ⊆ A, define the characteristic function:

χ_B : A → {0,1}

χ_B(x) = 1  if x ∈ B
χ_B(x) = 0  if x ∉ B

Each subset corresponds to a function from A to {0,1}, and vice versa. Therefore:

𝒫(A) is in one-to-one correspondence with {0,1}^A

Bitmasks, permission masks, and Boolean feature vectors all use this correspondence. Encoding convenience does not imply semantic clarity: when bits exceed the width of a machine word, permissions require hierarchy, or new bits must be added in the future, versioning and compatibility concerns arise.

More generally, B^A denotes all functions from A to B. For finite sizes n and m, each input independently chooses an output, giving mⁿ functions. An empty domain has exactly one empty function; a nonempty domain has no function to an empty codomain. Thus 0⁰=1 in this counting convention, without making a claim about real-valued limits.

Ordered Pairs and Cartesian Product

Sets are unordered, but ordered pairs (a,b) distinguish between the first and second positions. Typically:

(a,b) = (c,d)  ⇔  a=c ∧ b=d

The Cartesian product of sets A and B:

A × B = {(a,b) | a∈A ∧ b∈B}

For example:

A={alice,bob}
B={read,write}

A×B={
  (alice,read), (alice,write),
  (bob,read),   (bob,write)
}

An authorization relationship can be a subset of A×B: only the truly permitted user–permission pairs are retained. Chapter 5 will systematically expand on the idea that "a relation is a subset of a Cartesian product."

For finite sets:

|A × B| = |A| · |B|

When multiple input dimensions are multiplied together, a combinatorial explosion occurs. Configuration matrices, cross-browser testing, and parameterized queries must all be cautious about unbounded full Cartesian products.

Set Families and Union and Intersection

Sometimes you need to perform set operations on more than just two sets. Let a family of sets be indexed by I, with A_i ⊆ U for a fixed universe U:

{A_i | i ∈ I}

The union and intersection of such a family are written as:

⋃_{i∈I} A_i = {x ∈ U | ∃i∈I, x∈A_i}
⋂_{i∈I} A_i = {x ∈ U | ∀i∈I, x∈A_i}

For example, the union of multiple role-based permissions represents the set of permissions a user has if they are granted any one of the roles; the intersection represents the permissions shared by all roles.

The union over an empty index set is typically defined as the empty set. The intersection over an empty index set must be interpreted relative to a given domain and is generally taken to be the universal set. This aligns with the logical convention that an empty disjunction is false and an empty conjunction is true.

Comparing Cardinality Without Counting Every Element

The cardinality of a finite set |A| is the number of elements. Infinite sets cannot be counted individually, but their sizes can be compared using bijections.

If there exists a bijection f:A→B, then A and B have the same cardinality, denoted as:

|A| = |B|

The set of natural numbers ℕ and the set of even numbers 2ℕ have the same cardinality because:

f(n)=2n

It is both injective and surjective. Even numbers seem to constitute only "half" of the natural numbers, but intuitions about infinite cardinalities differ from finite proportions.

A set that can be put in one-to-one correspondence with ℕ is called countably infinite. The integers ℤ and the rational numbers ℚ are both countable; the real numbers ℝ are not.

Cantor's Theorem: The Power Set is Strictly Larger

For any set A, there is no surjective function from A to 𝒫(A), therefore:

The size comparison also uses the injection x ↦ {x}, which embeds A into 𝒫(A). Ruling out a surjection from A to 𝒫(A) also rules out a bijection, completing the strict inequality.

|A| < |𝒫(A)|

The proof uses diagonalization. Suppose f:A→𝒫(A) is a surjection. Define:

D = {x ∈ A | x ∉ f(x)}

Under the assumption of surjectivity, there must exist some d∈A such that f(d)=D. Now ask whether d ∈ D.

d ∈ D  ⇔  d ∉ f(d)  ⇔  d ∉ D

This contradiction shows that such a surjection cannot exist.

This is not just a clever trick. It demonstrates that even starting from an infinite set, taking the power set yields a strictly larger infinite cardinality.

Completion Checklist

Given A={a,b,c} and B={0,1}:

1. Write out 𝒫(A);
2. Encode each subset using a bit vector;
3. Write out A×B and B×A, and explain whether they are equal;
4. Represent a user's permission relationship as a subset of Users×Permissions;
5. Explain why 20 independent switches have 2²⁰ possible configurations;
6. State in one sentence why Cantor's diagonal set D cannot appear in the range of f.

References

• Open Logic Project