Set Theory

Set theory is the foundation of modern mathematics and computer science. Nearly every mathematical concept can be expressed in terms of sets.

Sets

A set is an unordered collection of distinct objects called elements (or members).

Notation:

a ∈ S — a is an element of S
a ∉ S — a is not an element of S

Specifying Sets

Roster notation (listing elements):

A = {1, 2, 3, 4, 5}
B = {a, b, c}

Set-builder notation (describing a property):

C = {x | x is a positive even integer}
D = {x ∈ ℤ | x² < 20} = {-4, -3, -2, -1, 0, 1, 2, 3, 4}

Interval notation (for real numbers):

[a, b] = {x ∈ ℝ | a ≤ x ≤ b}    (closed)
(a, b) = {x ∈ ℝ | a < x < b}     (open)
[a, b) = {x ∈ ℝ | a ≤ x < b}     (half-open)

| Symbol | Set | |---|---| | ∅ or {} | Empty set | | ℕ | Natural numbers {0, 1, 2, 3, ...} (sometimes starts at 1) | | ℤ | Integers {..., -2, -1, 0, 1, 2, ...} | | ℤ⁺ | Positive integers {1, 2, 3, ...} | | ℚ | Rational numbers {p/q | p, q ∈ ℤ, q ≠ 0} | | ℝ | Real numbers | | ℂ | Complex numbers | | 𝔹 | {0, 1} or {true, false} |

Set Properties

Unordered: {1, 2, 3} = {3, 1, 2}
No duplicates: {1, 1, 2} = {1, 2}
Elements can be anything: sets of numbers, sets of sets, sets of functions, etc.

Subsets

Subset: A ⊆ B if every element of A is also in B.

A ⊆ B ⟺ ∀x (x ∈ A → x ∈ B)

Proper subset: A ⊂ B if A ⊆ B and A ≠ B (i.e., B has at least one element not in A).

Set equality: A = B if and only if A ⊆ B and B ⊆ A.

Key facts:

∅ ⊆ A for every set A (vacuously true)
A ⊆ A for every set A

Power Set

The power set of S, written P(S) or 2^S, is the set of all subsets of S.

S = {a, b, c}
P(S) = {∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}

If |S| = n, then |P(S)| = 2ⁿ.

Proof by induction: Adding one element x to S doubles the subsets — for each existing subset T, we get both T and T ∪ {x}.

Cartesian Product

The Cartesian product of A and B:

A × B = {(a, b) | a ∈ A, b ∈ B}

Example:

A = {1, 2}, B = {x, y}
A × B = {(1,x), (1,y), (2,x), (2,y)}

Properties:

|A × B| = |A| · |B|
A × B ≠ B × A in general (unless A = B or one is empty)
A × ∅ = ∅

n-ary Cartesian product:

A₁ × A₂ × ... × Aₙ = {(a₁, a₂, ..., aₙ) | aᵢ ∈ Aᵢ for all i}

The Cartesian product ℝ × ℝ = ℝ² is the familiar 2D coordinate plane.

Set Operations

Set Operations and Identities

Union (∪)

A ∪ B = {x | x ∈ A ∨ x ∈ B}

Elements in A or B (or both).

Intersection (∩)

A ∩ B = {x | x ∈ A ∧ x ∈ B}

Elements in both A and B.

Two sets are disjoint if A ∩ B = ∅.

Difference (\)

A \ B = {x | x ∈ A ∧ x ∉ B}

Elements in A but not in B. Also written A - B.

Complement (A̅ or Aᶜ)

Aᶜ = U \ A = {x ∈ U | x ∉ A}

Everything in the universal set U that is not in A.

Symmetric Difference (△)

A △ B = (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B)

Elements in exactly one of A or B.

Venn Diagrams

Venn diagrams visually represent set operations. Each set is a circle, and the universal set is the enclosing rectangle.

    ┌───────────────────────┐
    │         U             │
    │    ┌─────┬─────┐      │
    │    │  A  │ A∩B │      │
    │    │only │     │      │
    │    │     │     │ B    │
    │    └─────┤only │      │
    │          └─────┘      │
    └───────────────────────┘

A ∪ B: everything inside either circle
A ∩ B: the overlapping region
A \ B: left crescent only
A △ B: both crescents

Set Identities

These parallel the logical equivalences from propositional logic:

Identity:

A ∪ ∅ = A
A ∩ U = A

Domination:

A ∪ U = U
A ∩ ∅ = ∅

Idempotent:

A ∪ A = A
A ∩ A = A

Complement:

A ∪ Aᶜ = U
A ∩ Aᶜ = ∅
(Aᶜ)ᶜ = A

Commutative:

A ∪ B = B ∪ A
A ∩ B = B ∩ A

Associative:

(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)

Distributive:

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Absorption:

A ∪ (A ∩ B) = A
A ∩ (A ∪ B) = A

De Morgan's Laws for Sets:

(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
(A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Proving Set Identities

Method 1: Element-chasing — Show x ∈ LHS ⟹ x ∈ RHS and vice versa.

Example: Prove A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

(⊆): Let x ∈ A ∩ (B ∪ C). Then x ∈ A and x ∈ B ∪ C. So x ∈ B or x ∈ C.

If x ∈ B: then x ∈ A ∩ B, so x ∈ (A ∩ B) ∪ (A ∩ C).
If x ∈ C: then x ∈ A ∩ C, so x ∈ (A ∩ B) ∪ (A ∩ C).

(⊇): Let x ∈ (A ∩ B) ∪ (A ∩ C). Then x ∈ A ∩ B or x ∈ A ∩ C.

Either way, x ∈ A. Also x ∈ B or x ∈ C, so x ∈ B ∪ C.
Therefore x ∈ A ∩ (B ∪ C). ∎

Method 2: Algebraic proof — Use known identities to transform one side into the other.

Method 3: Membership table — Like a truth table, assign 1 if element is in the set, 0 otherwise.

Generalized Operations

For a collection of sets A₁, A₂, ..., Aₙ:

⋃ᵢ₌₁ⁿ Aᵢ = A₁ ∪ A₂ ∪ ... ∪ Aₙ = {x | ∃i, x ∈ Aᵢ}
⋂ᵢ₌₁ⁿ Aᵢ = A₁ ∩ A₂ ∩ ... ∩ Aₙ = {x | ∀i, x ∈ Aᵢ}

Generalized De Morgan's:

(⋃ᵢ Aᵢ)ᶜ = ⋂ᵢ Aᵢᶜ
(⋂ᵢ Aᵢ)ᶜ = ⋃ᵢ Aᵢᶜ

Russell's Paradox

Naive set theory allows constructing "the set of all sets that don't contain themselves":

R = {S | S ∉ S}

Is R ∈ R?

If R ∈ R, then by definition R ∉ R. Contradiction.
If R ∉ R, then by definition R ∈ R. Contradiction.

This paradox showed that unrestricted set comprehension leads to contradictions. It motivated the development of axiomatic set theory (ZFC).

Axiomatic Set Theory (ZFC)

Zermelo-Fraenkel set theory with the Axiom of Choice (ZFC) provides a rigorous foundation. Key axioms:

Extensionality: Two sets are equal iff they have the same elements.
Empty Set: ∅ exists.
Pairing: For any a, b, the set {a, b} exists.
Union: For any set S, the union ⋃S exists.
Power Set: For any set S, the power set P(S) exists.
Separation (Comprehension): For any set S and property P, {x ∈ S | P(x)} exists. (Note: requires x ∈ S, avoiding Russell's paradox.)
Replacement: The image of a set under a definable function is a set.
Infinity: An infinite set exists (e.g., ℕ).
Foundation (Regularity): Every non-empty set has a ∈-minimal element (prevents x ∈ x).
Choice: For any collection of non-empty sets, there exists a function choosing one element from each.

Axiom of Choice

The Axiom of Choice (AC) states: Given any collection of non-empty sets, it is possible to select exactly one element from each set.

Formally: For any set S of non-empty sets, there exists a function f: S → ⋃S such that f(A) ∈ A for all A ∈ S.

AC seems intuitively obvious for finite collections, but for infinite collections it is non-trivial and independent of the other ZFC axioms.

Equivalent statements:

Zorn's Lemma: Every partially ordered set in which every chain has an upper bound contains a maximal element.
Well-Ordering Theorem: Every set can be well-ordered (Zermelo).
Every surjection has a right inverse.
Every vector space has a basis.
The product of non-empty sets is non-empty.

Controversial consequences:

The Banach-Tarski paradox: A solid ball can be decomposed into finitely many pieces and reassembled into two balls of the same size.

Zorn's Lemma

Zorn's Lemma: If every chain (totally ordered subset) in a partially ordered set P has an upper bound in P, then P has at least one maximal element.

Applications in CS and math:

Every vector space has a basis.
Every proper ideal in a ring is contained in a maximal ideal.
Proving the existence of certain graph colorings and matchings.

Multisets

A multiset (bag) is like a set but allows repeated elements.

M = {a, a, b, c, c, c}

The multiplicity of an element is how many times it appears: mult(a) = 2, mult(b) = 1, mult(c) = 3.

Multiset operations extend set operations by considering multiplicities.

Real-World Applications

Type theory: Types are essentially sets of values. Union types correspond to set union, intersection types to set intersection.
Databases: Relations are sets of tuples. SQL operations (UNION, INTERSECT, EXCEPT) correspond directly to set operations. (SQL bags/multisets allow duplicates by default.)
Access control: User permissions are sets. Access = UserRoles ∩ RequiredRoles.
Data structures: Sets are implemented as hash sets, tree sets, bit sets. Set operations are fundamental to algorithms.
Formal verification: Specifications describe sets of valid states. Model checking explores sets of reachable states.
Programming: Collection types in most languages (HashSet, BTreeSet, frozenset) implement mathematical sets.