Set Theory

Sets: The Foundation of Mathematics

A set is an unordered collection of distinct objects. Sets are described by membership: $x \in A$ means $x$ belongs to $A$.

Key Operations

Power Set

If $|A| = n$, then $|\mathcal{P}(A)| = 2^n$. Every element either is or isn't in a subset — $n$ binary choices.

def power_set(s):
    result = [frozenset()]
    for elem in sorted(s):
        result = result + [subset | {elem} for subset in result]
    return result

print(len(power_set({1, 2, 3})))  # 8 = 2^3

Cartesian Product

$|A \times B| = |A| \cdot |B|$ — the product rule for counting.

def cartesian_product(A, B):
    return [(a, b) for a in sorted(A) for b in sorted(B)]

print(len(cartesian_product({1, 2}, {3, 4, 5})))  # 6 = 2 × 3

Your Task

Implement power_set(s) and cartesian_product(A, B) as shown above.