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

The permission administrator provides three foundational permissions, but Ah Hua quickly realizes that the real audit concern is the full spectrum of possible permission combinations that can emerge from them.

A service has three permissions: read, write, and delete. While each individual permission set contains only three elements, the total number of possible permission combinations reaches eight. Sets are not just filters for existing objects, they also generate new conceptual spaces: the set of all subsets, the set of all pairs, and the set of all 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. Test strategies cannot hope to exhaustively explore all combinations, they must leverage constraints, coverage criteria, or generative methods to reduce the search space.

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 leverage 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.

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 an index set I:

{A_i | i ∈ I}

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

⋃_{i∈I} A_i = {x | ∃i∈I, x∈A_i}
⋂_{I∈I} A_i = {x | ∀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.

Base comparison Goes Beyond "counting until done"

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:

|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: is d∈D in 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