Sets and Set Theory Operations

Updated

September 7, 2026

Sets and Set Theory Operations

After reading this chapter, you will master Python’s hash set implementation (set and frozenset), execute mathematical set algebra for declarative state reconciliation, verify access permissions with subset operations, leverage \(O(1)\) membership testing, and avoid the empty set syntax trap.

Mental model

A Python set is a hash table that stores only unique keys without associated values. In CPython (PySetObject), each entry contains a hash code and a key pointer:

CPython PySetObject Architecture:
  Key: "node-01", hash % 8 = 2
  Key: "node-02", hash % 8 = 6

  Hash Table Slots:
  Slot:      0       1       2             3       4       5       6             7
  Entries: [ NULL,  NULL,  &"node-01",   NULL,   NULL,   NULL,  &"node-02",    NULL ]

Because lookups jump directly to the computed hash slot, membership testing (item in my_set) operates in amortized \(O(1)\) time, compared to \(O(N)\) linear scans in a list.

Set Theory Operations

Python supports both symbolic operators and named methods for standard set algebra:

Set A: { 1, 2, 3 }          Set B: { 3, 4, 5 }

Union (A | B):
  All unique elements in either set ──────────────▶ { 1, 2, 3, 4, 5 }

Intersection (A & B):
  Elements present in both sets ──────────────────▶ { 3 }

Difference (A - B):
  Elements in A but NOT in B ─────────────────────▶ { 1, 2 }

Symmetric Difference (A ^ B):
  Elements in exactly one set, but not both ──────▶ { 1, 2, 4, 5 }

Minimal example

Save as set_mechanics.py:

# set_mechanics.py
import sys
import time

def main() -> None:
    # 1. Syntax distinction: {} is a dict, set() is an empty set
    empty_dict = {}
    empty_set  = set()
    print(f"Type of {{}}:    {type(empty_dict).__name__}")
    print(f"Type of set(): {type(empty_set).__name__}")

    # 2. Deduplication and set algebra
    raw_tags = ["prod", "web", "us-east", "web", "prod", "api"]
    unique_tags = set(raw_tags)
    print(f"\nDeduplicated tags: {sorted(unique_tags)}")

    # 3. O(1) membership testing vs O(N) list search
    n = 100_000
    target = n - 1
    num_list = list(range(n))
    num_set  = set(range(n))

    # Benchmark list search (O(N))
    start = time.perf_counter()
    _ = target in num_list
    list_time = time.perf_counter() - start

    # Benchmark set search (O(1))
    start = time.perf_counter()
    _ = target in num_set
    set_time = time.perf_counter() - start

    print(f"\nMembership check for {n:,} items:")
    print(f"  List search time: {list_time * 1_000_000:.2f} µs")
    print(f"  Set  search time: {set_time  * 1_000_000:.2f} µs  ({list_time / set_time:.1f}x faster)")

if __name__ == "__main__":
    main()

Run via uv run python set_mechanics.py:

Type of {}:    dict
Type of set(): set

Deduplicated tags: ['api', 'prod', 'us-east', 'web']

Membership check for 100,000 items:
  List search time: 820.50 µs
  Set  search time: 0.12 µs  (6837.5x faster)

Worked examples

Case 1: Declarative Infrastructure State Reconciliation

In Site Reliability Engineering (SRE) and Kubernetes controllers, reconciliation loops continually compute the difference between the desired state (from Git/YAML) and the actual state (from the live cloud provider):

# cluster_reconciler.py
def reconcile_cluster_nodes(actual: set[str], desired: set[str]) -> None:
    """Determine which cloud instances to provision, terminate, or preserve."""
    to_terminate   = actual - desired     # Running nodes no longer wanted
    to_provision   = desired - actual     # Required nodes not yet running
    stable_healthy = actual & desired     # Nodes already conforming to spec

    print("--- Infrastructure Reconciliation Plan ---")
    print(f"Stable nodes    (&): {sorted(stable_healthy)}")
    print(f"To provision    (+): {sorted(to_provision)}")
    print(f"To terminate    (-): {sorted(to_terminate)}")

def main() -> None:
    live_instances    = {"srv-1", "srv-2", "srv-3", "srv-legacy"}
    desired_manifest  = {"srv-2", "srv-3", "srv-4", "srv-5"}

    reconcile_cluster_nodes(actual=live_instances, desired=desired_manifest)

if __name__ == "__main__":
    main()

Run:

uv run python cluster_reconciler.py

Output:

--- Infrastructure Reconciliation Plan ---
Stable nodes    (&): ['srv-2', 'srv-3']
To provision    (+): ['srv-4', 'srv-5']
To terminate    (-): ['srv-1', 'srv-legacy']

Case 2: Role-Based Access Control (RBAC) with Subset Checks

Verifying whether a user possesses all required security permissions can be expressed cleanly as a subset evaluation (required <= user_permissions):

# rbac_validator.py
def check_authorization(
    user_roles: set[str],
    endpoint_required_roles: set[str],
) -> bool:
    """Return True if user possesses ALL required permissions for an action."""
    # The <= operator tests if endpoint_required_roles is a subset of user_roles
    return endpoint_required_roles <= user_roles

def main() -> None:
    alice_permissions = {"read:reports", "write:reports", "read:users"}
    bob_permissions   = {"read:reports"}

    # Operations requiring multiple simultaneous privileges
    admin_action = {"read:reports", "write:reports"}
    audit_action = {"read:audit_logs"}

    print("Authorization Check Results:")
    print(f"  Alice performing Admin action: {check_authorization(alice_permissions, admin_action)}")
    print(f"  Bob   performing Admin action: {check_authorization(bob_permissions, admin_action)}")
    print(f"  Alice performing Audit action: {check_authorization(alice_permissions, audit_action)}")

if __name__ == "__main__":
    main()

Run:

uv run python rbac_validator.py

Output:

Authorization Check Results:
  Alice performing Admin action: True
  Bob   performing Admin action: False
  Alice performing Audit action: False

Case 3: Immutable Sets with `frozenset` as Dictionary Keys

Because a standard set is mutable, its hash is uncomputable and it cannot serve as a dictionary key or set member. Python provides frozenset for immutable set contexts:

# frozenset_cache.py
from collections.abc import Callable

def main() -> None:
    # Memoization cache where key is an unordered group of tags
    # Example: cache[(tag_a, tag_b)] where order should not matter!
    tag_rule_cache: dict[frozenset[str], str] = {}

    tags_req_1 = frozenset(["auth", "production", "eu-west"])
    tags_req_2 = frozenset(["eu-west", "auth", "production"])  # Identical elements, different order!

    tag_rule_cache[tags_req_1] = "POLICY_STRICT_GDPR"

    # Both lookups match the identical frozenset key
    print(f"Rule for req 1: {tag_rule_cache[tags_req_1]}")
    print(f"Rule for req 2: {tag_rule_cache[tags_req_2]}")
    print(f"Are frozenset keys identical? {tags_req_1 == tags_req_2}")

if __name__ == "__main__":
    main()

Run:

uv run python frozenset_cache.py

Output:

Rule for req 1: POLICY_STRICT_GDPR
Rule for req 2: POLICY_STRICT_GDPR
Are frozenset keys identical? True

Pitfalls

Pitfall 1: The Empty Set Syntax Trap (`{}` vs `set()`)

Because curly braces {} were introduced for dictionaries before sets were added to Python, {} creates a dictionary, NOT a set:

# THE TRAP:
s = {}
print(f"Type: {type(s)}")  # <class 'dict'>
# s.add(10)                # AttributeError: 'dict' object has no attribute 'add'

# THE FIX: Always use set() for an empty set
s = set()
s.add(10)
print(f"Type: {type(s)}, Contents: {s}")  # <class 'set'>, Contents: {10}

Pitfall 2: Adding Mutable Objects to a Set

Sets require elements to be hashable. Attempting to add a list or dictionary raises TypeError:

# THE TRAP:
try:
    bad_set = { [1, 2], [3, 4] }
except TypeError as err:
    print(f"Hash error: {err}")  # TypeError: unhashable type: 'list'

# THE FIX: Store immutable tuples
good_set = { (1, 2), (3, 4) }
print(f"Valid set: {good_set}")

Pitfall 3: Mutating a Set While Iterating

Just like dictionaries, sets raise RuntimeError if an item is added or removed during iteration:

# THE TRAP:
tags = {"web", "prod", "legacy", "test"}
try:
    for tag in tags:
        if "legacy" in tag:
            tags.remove(tag)
except RuntimeError as err:
    print(f"Caught: {err}")  # Set changed size during iteration

# THE FIX: Filter into a new set or iterate over a set snapshot
tags = {"web", "prod", "legacy", "test"}
tags = {tag for tag in tags if "legacy" not in tag}
print(f"Cleaned tags: {tags}")

Exercises

Given a list of user IP addresses ["192.168.1.1", "10.0.0.1", "192.168.1.1", "172.16.0.5"], extract all unique IPs and print the total unique visitor count.
Given two sets service_a_deps = {"db", "redis", "auth"} and service_b_deps = {"db", "kafka", "billing"}, compute their shared dependencies, unique dependencies to service_a, and the total combined dependencies.
Demonstrate why frozenset can be added as an element of another set, but a standard set cannot.
Write a function is_valid_packet(headers: set[str]) -> bool that verifies whether a packet contains all three mandatory headers: "SRC", "DST", and "TTL".
Benchmark the time to check 999_999 in collection between a list of 1,000,000 numbers and a set of 1,000,000 numbers.

Sets and Set Theory Operations

Mental model

Set Theory Operations

Minimal example

Worked examples

Case 1: Declarative Infrastructure State Reconciliation

Case 2: Role-Based Access Control (RBAC) with Subset Checks

Case 3: Immutable Sets with frozenset as Dictionary Keys

Pitfalls

Pitfall 1: The Empty Set Syntax Trap ({} vs set())

Pitfall 2: Adding Mutable Objects to a Set

Pitfall 3: Mutating a Set While Iterating

Exercises

Further reading

Case 3: Immutable Sets with `frozenset` as Dictionary Keys

Pitfall 1: The Empty Set Syntax Trap (`{}` vs `set()`)