Part 2: Set Theory & Foundations

Why Set Theory for ML?

Before learning probability, you need sets. Before defining a feature space, you need sets. Before talking about "predicted class A" or "ground truth label B", you need sets. Set theory is the bedrock of the mathematical language used across all of ML.

Sets and Notation

A set is an unordered collection of distinct objects (called elements or members). The key properties: order doesn't matter, and elements can't repeat.

The second form uses set-builder notation: "$B$ is the set of all real numbers $x$ such that $x > 0$" — this is how infinite sets are described compactly.

1 — Membership & Cardinality

Membership: $x \in A$ means "$x$ is an element of $A$". Its negation: $x \notin A$.

Cardinality $|A|$ is the number of elements in set $A$:

The empty set $\emptyset = \{\}$ contains no elements. It is a subset of every set (by vacuous truth).

2 — Subsets & Power Sets

$A$ is a subset of $B$, written $A \subseteq B$, if every element of $A$ is also in $B$:

If additionally $B$ has elements not in $A$, it's a proper subset: $A \subsetneq B$.

The power set $\mathcal{P}(A)$ is the set of ALL subsets of $A$ (including $\emptyset$ and $A$ itself):

The size of the power set grows exponentially:

3 — Special Number Sets

Note: $\mathbb{N} \subsetneq \mathbb{Z} \subsetneq \mathbb{Q} \subsetneq \mathbb{R}$ — each is a proper subset of the next.

## Python sets — basic operations
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

# Membership
print(3 in A)       # True
print(7 in A)       # False

# Cardinality
print(len(A))       # 4

# Subset check
print({1, 2} <= A)  # True  (subset)
print({1, 2} < A)   # True  (proper subset)

# Power set (manual implementation)
def power_set(s):
    s = list(s)
    result = [[]]
    for elem in s:
        result += [subset + [elem] for subset in result]
    return [set(x) for x in result]

ps = power_set({1, 2, 3})
print(f"Power set size: {len(ps)}")  # 8 = 2^3
for s in sorted(ps, key=len):
    print(s)

Universal Set

The universal set $\mathcal{U}$ is the "master set" containing ALL objects under discussion in a given context. Every other set in the problem is automatically a subset of $\mathcal{U}$.

In probability, $\mathcal{U}$ directly corresponds to the sample space $\Omega$ — the set of all possible outcomes. Complement always depends on $\mathcal{U}$: if $\mathcal{U} = \{1,2,3,4,5\}$ and $A = \{1,2\}$, then $A^c = \{3,4,5\}$. Change $\mathcal{U}$ and you change the complement.

Singleton Set & Empty (Null) Set

A singleton set is a set with exactly one element:

The empty set (also called the null set) $\emptyset = \{\}$ contains no elements at all: $|\emptyset| = 0$. Key properties:

The empty set appears in ML when: a filter returns no results, two disjoint classes have no overlap, or a search returns no valid solutions. It is the unique set of cardinality 0.

Set Builder Notation

Set builder notation defines a set by a rule (a property members must satisfy) rather than listing elements individually. It is essential for defining infinite sets and feature spaces:

import numpy as np

# Set builder notation ↔ Python list/set comprehensions
# "All even numbers from 0 to 20"
even_numbers = {x for x in range(0, 21) if x % 2 == 0}
print("Even numbers:", sorted(even_numbers))
# {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}

# "All real x in [-3, 3] such that x^2 < 4"
xs = np.linspace(-3, 3, 1000)
satisfying = xs[xs**2 < 4]
print(f"\nx in [-3,3] satisfying x^2 < 4: range ({satisfying.min():.3f}, {satisfying.max():.3f})")
# Mathematically: (-2, 2)

# Feature filtering — select features with |correlation| > 0.5
correlations = {'age': 0.72, 'income': 0.61, 'height': 0.12, 'weight': 0.08, 'score': 0.89}
high_corr = {f for f, c in correlations.items() if abs(c) > 0.5}
print(f"\nHighly correlated features: {high_corr}")
# {'age', 'income', 'score'}

Equal & Equivalent Sets

These are two distinct relationships beginners frequently confuse:

Equal sets contain exactly the same elements (order does not matter in sets):

Equivalent sets (also called equinumerous) have the same cardinality but may contain completely different elements:

# Equal sets: same elements regardless of order
A = {1, 2, 3}
B = {3, 2, 1}   # same elements
C = {'cat', 'dog', 'fish'}  # same size, different elements

print("A == B:", A == B)              # True — equal (same elements)
print("A == C:", A == C)              # False — not equal
print("|A| == |C|:", len(A) == len(C))  # True — equivalent (same cardinality)

# ML context: predicted classes vs actual class labels
predicted = {0, 1, 2}                 # numeric class indices
actual_names = {'cat', 'dog', 'bird'} # string class names
print("\nSame number of classes:", len(predicted) == len(actual_names))  # True
print("Same class sets:", predicted == actual_names)  # False — equivalent, not equal

Proper Subsets, Improper Subsets & Supersets

The general concept of "subset" has important subtypes that appear frequently in formal ML writing:

# Python set comparison operators
A = frozenset({1, 2})
B = frozenset({1, 2, 3})

print("A ⊆ B  (subset):",         A <= B)   # True
print("A ⊂ B  (proper subset):",  A < B)    # True — A ≠ B
print("B ⊆ A  (subset):",         B <= A)   # False
print("B ⊇ A  (superset):",       B >= A)   # True
print("B ⊃ A  (proper superset):", B > A)   # True
print("A ⊆ A  (improper):",       A <= A)   # True — every set is its own subset
print("A ⊂ A  (proper):",         A < A)    # False — no proper subset of itself

Finite & Infinite Sets

A finite set has a specific, countable number of elements ($|A| = n$ for some $n \in \mathbb{N}$). An infinite set continues without bound.

Set Operations

Set operations are the algebraic tools for combining and manipulating sets. They have direct parallels in Boolean logic and SQL WHERE clauses.

4 — Union & Intersection

Union $A \cup B$: all elements in $A$ OR in $B$ (or both):

Intersection $A \cap B$: all elements in BOTH $A$ AND $B$:

Two sets are disjoint if $A \cap B = \emptyset$.

flowchart LR
    A["Set A\n{1,2,3,4}"] --> U["A ∪ B\n{1,2,3,4,5,6}\nOR — everything"]
    B["Set B\n{3,4,5,6}"] --> U
    A --> I["A ∩ B\n{3,4}\nAND — overlap only"]
    B --> I
    A --> D["A \\ B\n{1,2}\nIN A but NOT B"]
    B --> D
    A --> S["A △ B\n{1,2,5,6}\nXOR — one but not both"]
    B --> S

    style A fill:#e8f4f4,stroke:#3B9797,color:#132440
    style B fill:#f0f4f8,stroke:#16476A,color:#132440
    style U fill:#d4edda,stroke:#3B9797,color:#132440
    style I fill:#fff3cd,stroke:#F5A623,color:#132440
    style D fill:#fde8ec,stroke:#BF092F,color:#132440
    style S fill:#e8e0f0,stroke:#6f42c1,color:#132440
                            

5 — Complement & Set Difference

The complement $A^c$ (also written $\bar{A}$ or $A'$) is everything in the universal set $\mathcal{U}$ that is NOT in $A$:

Set difference $A \setminus B$ (also $A - B$) removes elements of $B$ from $A$:

Symmetric difference $A \triangle B$: elements in exactly one of $A$ or $B$:

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

print("Union:", A | B)              # {1, 2, 3, 4, 5, 6}
print("Intersection:", A & B)       # {3, 4}
print("Difference A-B:", A - B)     # {1, 2}
print("Difference B-A:", B - A)     # {5, 6}
print("Symmetric diff:", A ^ B)     # {1, 2, 5, 6}

# Complement requires knowing the universal set
U = set(range(1, 11))  # Universal set: {1,...,10}
A_complement = U - A
print("Complement of A:", A_complement)  # {5, 6, 7, 8, 9, 10}

6 — The Inclusion-Exclusion Principle

When counting elements in a union, naively adding $|A|$ and $|B|$ double-counts the intersection:

For three sets:

Venn Diagrams

A Venn diagram is a visual tool for representing sets as overlapping circles inside a rectangle (the universal set). They make set relationships immediately intuitive — especially for beginners.

Standard layout: the rectangle = $\mathcal{U}$, each circle = one set, overlapping regions = intersections.

Venn diagrams are powerful for verifying set identities visually. To check De Morgan's Law $(A \cup B)^c = A^c \cap B^c$: shade $A \cup B$ (both circles), then take its complement (everything outside both circles). This exactly equals the region outside A AND outside B — confirming the law.

Laws of Sets

Set theory has a complete algebra with named laws — analogous to arithmetic laws for numbers. These laws let you simplify complex expressions and are the mathematical foundation of Boolean logic (the basis of all digital computing and ML decision conditions).

# Verify Laws of Sets programmatically
U = frozenset(range(1, 11))  # Universal set: {1,...,10}
A = frozenset({1, 2, 3, 4, 5})
B = frozenset({3, 4, 5, 6, 7})
C = frozenset({5, 6, 7, 8, 9})
Ac = U - A
Bc = U - B

# Commutative
assert A | B == B | A and A & B == B & A
print("Commutative: A∪B = B∪A and A∩B = B∩A  ✓")

# Associative
assert (A | B) | C == A | (B | C)
assert (A & B) & C == A & (B & C)
print("Associative: (A∪B)∪C = A∪(B∪C)  ✓")

# Distributive
assert A | (B & C) == (A | B) & (A | C)
assert A & (B | C) == (A & B) | (A & C)
print("Distributive: A∪(B∩C) = (A∪B)∩(A∪C)  ✓")

# Identity and Domination
assert A | frozenset() == A and A & U == A
assert A | U == U and A & frozenset() == frozenset()
print("Identity and Domination: ✓")

# Complement
assert A | Ac == U and A & Ac == frozenset()
print("Complement: A∪Aᶜ = U and A∩Aᶜ = ∅  ✓")

# De Morgan's
assert U - (A | B) == Ac & Bc  # (A∪B)^c = A^c ∩ B^c
assert U - (A & B) == Ac | Bc  # (A∩B)^c = A^c ∪ B^c
print("De Morgan's: both laws verified  ✓")

# Absorption
assert A | (A & B) == A and A & (A | B) == A
print("Absorption: A∪(A∩B) = A  ✓")

De Morgan's Laws

De Morgan's Laws are among the most useful identities in set theory — and they appear directly in Boolean logic, probability, and decision tree conditions.

Reading Law 1: "NOT (A or B)" is the same as "NOT A AND NOT B." If an email is neither spam nor phishing, that's the same as "it's not spam" AND "it's not phishing."

Reading Law 2: "NOT (A and B)" is the same as "NOT A OR NOT B." If a transaction is not (large AND international), then it's either not large OR not international.

U = set(range(1, 11))   # Universal set: 1..10
A = {1, 2, 3, 4, 5}
B = {3, 4, 5, 6, 7}

# De Morgan's Law 1: (A ∪ B)^c = A^c ∩ B^c
left_1  = U - (A | B)
right_1 = (U - A) & (U - B)
print("Law 1 holds:", left_1 == right_1)  # True
print("(A ∪ B)^c =", left_1)             # {8, 9, 10}

# De Morgan's Law 2: (A ∩ B)^c = A^c ∪ B^c
left_2  = U - (A & B)
right_2 = (U - A) | (U - B)
print("Law 2 holds:", left_2 == right_2)  # True
print("(A ∩ B)^c =", left_2)             # {1, 2, 6, 7, 8, 9, 10}

Cartesian Products & Feature Spaces

The Cartesian product $A \times B$ creates a new set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$:

Mixed feature spaces are also Cartesian products. A dataset with 3 numeric features and 2 binary categorical features lives in $\mathbb{R}^3 \times \{0,1\}^2$.

import itertools

# Cartesian product of two sets
A = {1, 2, 3}
B = {'a', 'b'}
AxB = list(itertools.product(A, B))
print("A × B:", AxB)
print("|A × B| =", len(AxB))          # 6 = 3 × 2

# Feature space example: 2 continuous + 1 binary feature
# A data point from R × R × {0,1}
data_point = (3.14, -0.5, 1)           # (income, credit_score, employed)
print("Feature vector:", data_point)

# Cartesian product for hyperparameter grid search
learning_rates = [0.001, 0.01, 0.1]
hidden_sizes   = [32, 64, 128]
grid = list(itertools.product(learning_rates, hidden_sizes))
print(f"\nHyperparameter grid ({len(grid)} combinations):")
for lr, hs in grid:
    print(f"  lr={lr}, hidden_size={hs}")

Partitions & ML Decision Regions

A partition of set $S$ is a collection of non-empty subsets $\{A_1, A_2, \ldots, A_k\}$ such that:

flowchart TD
    FS["Feature Space ℝ^d\n(All possible inputs)"]
    FS --> R1["Region R₁\n(Class A predictions)"]
    FS --> R2["Region R₂\n(Class B predictions)"]
    FS --> R3["Region R₃\n(Class C predictions)"]
    
    R1 --> P1["R₁ ∩ R₂ = ∅\nDisjoint"]
    R2 --> P1
    R2 --> P2["R₁ ∪ R₂ ∪ R₃ = ℝ^d\nEvery point classified"]
    R1 --> P2
    R3 --> P2

    style FS fill:#132440,stroke:#132440,color:#fff
    style R1 fill:#e8f4f4,stroke:#3B9797,color:#132440
    style R2 fill:#f0f4f8,stroke:#16476A,color:#132440
    style R3 fill:#fff5f5,stroke:#BF092F,color:#132440
    style P1 fill:#d4edda,stroke:#3B9797,color:#132440
    style P2 fill:#d4edda,stroke:#3B9797,color:#132440
                            

A $k$-class classifier implicitly partitions $\mathbb{R}^d$ into $k$ decision regions. The decision boundaries are the borders between these regions. For a linear classifier, each region is a convex polytope; for a neural network, the regions can be arbitrarily shaped.

Jaccard Similarity & Set-Based Distance

The Jaccard similarity measures how much two sets overlap, on a scale from 0 (no overlap) to 1 (identical):

Its complement, the Jaccard distance: $d_J(A, B) = 1 - J(A, B)$.

def jaccard_similarity(A, B):
    """Jaccard similarity between two sets."""
    intersection = len(A & B)
    union = len(A | B)
    if union == 0:
        return 1.0  # both empty sets are identical
    return intersection / union

def jaccard_distance(A, B):
    return 1 - jaccard_similarity(A, B)

# Document similarity example
doc1_words = {"machine", "learning", "neural", "network", "deep"}
doc2_words = {"machine", "learning", "algorithm", "model", "deep"}
doc3_words = {"cooking", "recipe", "pasta", "sauce", "italian"}

print(f"doc1 vs doc2: {jaccard_similarity(doc1_words, doc2_words):.3f}")  # ~0.43
print(f"doc1 vs doc3: {jaccard_similarity(doc1_words, doc3_words):.3f}")  # 0.0

# Object detection IoU
def iou(box_pred, box_true):
    """
    box = (x1, y1, x2, y2) — top-left and bottom-right corners
    Returns Intersection over Union (Jaccard for 2D boxes)
    """
    xi1 = max(box_pred[0], box_true[0])
    yi1 = max(box_pred[1], box_true[1])
    xi2 = min(box_pred[2], box_true[2])
    yi2 = min(box_pred[3], box_true[3])

    inter_area = max(0, xi2 - xi1) * max(0, yi2 - yi1)
    pred_area  = (box_pred[2]-box_pred[0]) * (box_pred[3]-box_pred[1])
    true_area  = (box_true[2]-box_true[0]) * (box_true[3]-box_true[1])
    union_area = pred_area + true_area - inter_area

    return inter_area / union_area if union_area > 0 else 0.0

predicted = (50, 50, 150, 150)
ground_truth = (75, 75, 175, 175)
print(f"\nIoU: {iou(predicted, ground_truth):.3f}")  # 0.143

Practice Exercises

Conclusion & Next Steps

Set theory gives us a precise language for talking about collections, membership, and relationships. The key takeaways:

• Sets are unordered, distinct collections — the atoms of probability and feature spaces
• Power sets grow as $2^{|A|}$ — explaining why exhaustive search over features is impossible
• Operations (union ∪, intersection ∩, complement, difference) have direct parallels in Boolean logic, SQL, and ML evaluation
• De Morgan's Laws let you convert OR conditions to AND conditions and vice versa
• Cartesian products define feature spaces — your data lives in $\mathbb{R}^d$
• Partitions are what classifiers create — disjoint regions covering the entire input space
• Jaccard / IoU quantifies set similarity — fundamental to recommendation and detection tasks