Set Theory

Set Theory

Set Definition

Sets are typically denoted with curly braces. For example:

Set Operations

Summary Table

Venn Diagrams

Venn diagrams are visual representations of set relationships. They use overlapping circles (or other shapes) inside a rectangle representing the universal set $U$.

• Two-set Venn: Two overlapping circles. The overlap is $A \cap B$. The region in $A$ but outside $B$ is $A \setminus B$.
• Three-set Venn: Three overlapping circles create 8 distinct regions (including the outside region). This is useful for visualizing relationships among three sets.
• Disjoint sets: Two sets with no overlap, $A \cap B = \emptyset$, are represented as non-overlapping circles.
• Subset: If $A \subseteq B$, the circle for $A$ is drawn entirely inside the circle for $B$.

Venn diagrams are widely used in probability theory, database query visualization, survey analysis, and data science exploratory analysis.

Power Set

def power_set(s):
    """Generate all subsets of set s."""
    result = [[]]
    for elem in s:
        result = result + [subset + [elem] for subset in result]
    return result

A = {1, 2, 3}
ps = power_set(list(A))
print(f"Power set of {A}:")
for subset in ps:
    print(subset)
print(f"Total subsets: {len(ps)}")  # 8

Cartesian Product

The Cartesian product is fundamental to defining relations, functions, and the structure of coordinate systems. In databases, it underlies the concept of a cross join. In machine learning, feature spaces are Cartesian products of individual feature domains.

Partitions

Partitions are critical in probability (events that partition the sample space), database design (table normalization), and clustering algorithms (each data point belongs to exactly one cluster).

Inclusion-Exclusion Principle

Python Implementation

from itertools import combinations
from functools import reduce

# Basic set operations
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8}

# Union
print(f"A ∪ B = {A | B}")              # {1, 2, 3, 4, 5, 6, 7, 8}

# Intersection
print(f"A ∩ B = {A & B}")              # {4, 5}

# Difference
print(f"A - B = {A - B}")             # {1, 2, 3}
print(f"B - A = {B - A}")             # {6, 7, 8}

# Symmetric Difference
print(f"A △ B = {A ^ B}")             # {1, 2, 3, 6, 7, 8}

# Complement (given a universal set)
U = set(range(1, 11))
print(f"Aᶜ = {U - A}")               # {6, 7, 8, 9, 10}

# Power Set
def power_set(s):
    """Generate all subsets of set s."""
    result = [[]]
    for elem in s:
        result = result + [subset + [elem] for subset in result]
    return result

A_list = [1, 2, 3]
ps = power_set(A_list)
print(f"\nPower set of {A_list}: {len(ps)} subsets")
for subset in ps:
    print(f"  {subset}")

# Cartesian Product
def cartesian_product(set_a, set_b):
    """Compute the Cartesian product of two sets."""
    return {(a, b) for a in set_a for b in set_b}

X = {1, 2}
Y = {'a', 'b', 'c'}
cp = cartesian_product(X, Y)
print(f"\nX × Y = {cp}")
print(f"|X × Y| = {len(cp)}")

# Inclusion-Exclusion
def inclusion_exclusion_two(set_a, set_b):
    """|A ∪ B| using inclusion-exclusion."""
    return len(set_a) + len(set_b) - len(set_a & set_b)

A_sets = {1, 2, 3, 4, 5}
B_sets = {4, 5, 6, 7}
print(f"\n|A ∪ B| = {inclusion_exclusion_two(A_sets, B_sets)}")

# Partition check
def is_partition(sets, universe):
    """Check if sets form a partition of universe."""
    flat = set()
    for s in sets:
        if not s:
            return False
        flat |= s
    if flat != universe:
        return False
    for i, s1 in enumerate(sets):
        for j, s2 in enumerate(sets):
            if i < j and s1 & s2:
                return False
    return True

U = {1, 2, 3, 4, 5, 6}
parts = [{1, 3}, {2, 5}, {4, 6}]
print(f"\nIs partition? {is_partition(parts, U)}")  # True

# Equivalence relation and partition
def equivalence_classes(relation, elements):
    """Group elements into equivalence classes."""
    visited = set()
    classes = []
    for e in elements:
        if e not in visited:
            cls = {x for x in elements if (e, x) in relation}
            classes.append(cls)
            visited |= cls
    return classes

# Parity equivalence: (a,b) in relation if a ≡ b (mod 2)
rel = {(a, b) for a in range(6) for b in range(6) if a % 2 == b % 2}
elements = set(range(6))
print(f"Equivalence classes (mod 2): {equivalence_classes(rel, elements)}")

Applications in AI/ML

Feature Engineering

In machine learning, features are often subsets of a larger feature space. Set operations enable efficient feature engineering:

• Feature selection identifies a subset $F \subseteq \{f_1, f_2, \ldots, f_n\}$ of relevant features. The power set of all features has size $2^n$, making exhaustive search intractable for large $n$.
• Set intersection identifies features shared across multiple datasets or models.
• Set difference finds features unique to one dataset, aiding in anomaly detection.
• Cartesian product constructs multi-dimensional feature spaces. If feature $X$ takes 5 values and feature $Y$ takes 10 values, the joint feature space has $5 \times 10 = 50$ possible combinations.
• Partitions form the basis of clustering. K-means partitions data points into $k$ groups, where each point belongs to exactly one cluster. Decision trees partition the feature space into regions with distinct class distributions.
• Inclusion-exclusion is used in probabilistic graphical models to avoid double-counting when computing joint probabilities over overlapping event sets.
• Power sets appear in model selection. The set of all possible feature subsets is $\mathcal{P}(\text{features})$, and subset selection algorithms (greedy forward selection, backward elimination) search this space.

Database Queries

SQL directly implements set operations:

-- UNION (set union)
SELECT name FROM employees UNION SELECT name FROM contractors;

-- INTERSECT (set intersection)
SELECT name FROM employees INTERSECT SELECT name FROM managers;

-- EXCEPT (set difference)
SELECT name FROM employees EXCEPT SELECT name FROM fired;

-- CROSS JOIN (Cartesian product)
SELECT * FROM colors CROSS JOIN sizes;

Probability

Set theory underpins probability. Events are subsets of a sample space $\Omega$. The probability of event $A$ is a measure $P: 2^\Omega \rightarrow [0, 1]$. Inclusion-exclusion computes $P(A \cup B)$ without double-counting.

Common Mistakes

Interview Questions

Practice Problems

Quick Reference

Cross-References

• Boolean Algebra: Set operations mirror logical operations. Union corresponds to OR, intersection to AND, complement to NOT. This connection powers digital circuit design and search engines.
• Probability Theory: Events are subsets of a sample space. $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ is the probabilistic form of inclusion-exclusion.
• Database Theory: SQL UNION, INTERSECT, and EXCEPT directly implement set operations. Understanding set theory is essential for writing correct and efficient queries.
• Graph Theory: Vertex and edge sets define graphs. Graph isomorphism checks whether two graphs have the same edge set.
• Linear Algebra — The set of solutions to a homogeneous linear system forms a vector space (a special kind of set closed under addition and scalar multiplication).
• Formal Languages: Languages are sets of strings. Regular expressions, context-free grammars, and automata all operate on sets of strings.
• Combinatorics — Counting techniques rely on partitions, inclusion-exclusion, and the pigeonhole principle—all rooted in set theory.
• Machine Learning — Feature spaces, label sets, training/test splits, and ensemble methods all involve partitioning data into sets.