Friday Night Wiki
TopicsAbout
Buy me a coffee
Computer Science Fundamentals

Set Theory

Introduction

Set theory is the mathematical study of collections of objects. It provides the language and foundation for nearly all of mathematics and computer science. From database queries to type systems, understanding sets is essential.

Learning Objectives

By the end of this reading, you will be able to:

  • Define sets using various notations
  • Perform set operations (union, intersection, difference, complement)
  • Understand subsets, power sets, and Cartesian products
  • Apply set identities to simplify expressions
  • Connect set theory to programming concepts

1. What is a Set?

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

Notation

  • Curly braces denote sets: A = {1, 2, 3}
  • Element membership: 2 ∈ A (2 is in A), 5 ∉ A (5 is not in A)
  • Sets are unordered: {1, 2, 3} = {3, 1, 2}
  • No duplicates: {1, 1, 2} = {1, 2}

Ways to Define Sets

Roster/Enumeration:

  • A = {1, 2, 3, 4, 5}
  • B = {a, e, i, o, u}

Set-Builder Notation:

  • A = {x | x is a positive integer less than 6}
  • B = {x ∈ ℤ | x² < 10} = {-3, -2, -1, 0, 1, 2, 3}

Interval Notation (for real numbers):

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

Special Sets

  • ∅ or {}: Empty set (contains no elements)
  • ℕ: Natural numbers {0, 1, 2, 3, ...} or {1, 2, 3, ...}
  • ℤ: Integers {..., -2, -1, 0, 1, 2, ...}
  • ℚ: Rational numbers (fractions p/q where p, q ∈ ℤ, q ≠ 0)
  • ℝ: Real numbers
  • ℂ: Complex numbers

2. Set Relationships

Subsets

A is a subset of B (written A ⊆ B) if every element of A is also in B.

Examples:

  • {1, 2} ⊆ {1, 2, 3} ✓
  • {1, 2, 3} ⊆ {1, 2, 3} ✓ (every set is a subset of itself)
  • ∅ ⊆ A (empty set is a subset of every set)

A is a proper subset of B (written A ⊂ B) if A ⊆ B and A ≠ B.

Set Equality

Two sets are equal if they contain exactly the same elements.

A = B if and only if A ⊆ B and B ⊆ A

Cardinality

The cardinality of a set is the number of elements it contains, written |A|.

  • |{1, 2, 3}| = 3
  • |∅| = 0
  • |{∅}| = 1 (set containing the empty set)

3. Set Operations

Union (∪)

The union of A and B contains all elements in A or B (or both).

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

Example:

  • {1, 2, 3} ∪ {3, 4, 5} = {1, 2, 3, 4, 5}

Intersection (∩)

The intersection of A and B contains elements in both A and B.

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

Example:

  • {1, 2, 3} ∩ {3, 4, 5} = {3}
  • If A ∩ B = ∅, sets A and B are disjoint

Difference (−)

The difference A − B contains elements in A but not in B.

A − B = {x | x ∈ A and x ∉ B}

Example:

  • {1, 2, 3} − {3, 4, 5} = {1, 2}

Complement (')

The complement of A contains all elements not in A (relative to a universal set U).

A' = U − A = {x ∈ U | x ∉ A}

Example:

  • If U = {1, 2, 3, 4, 5} and A = {1, 2}, then A' = {3, 4, 5}

Symmetric Difference (△)

The symmetric difference contains elements in A or B, but not both.

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

Example:

  • {1, 2, 3} △ {3, 4, 5} = {1, 2, 4, 5}

4. Venn Diagrams

Venn diagrams visualize set relationships.

        U (Universal Set)
    ┌─────────────────────┐
    │                     │
    │   ┌───┐   ┌───┐     │
    │   │ A │   │ B │     │
    │   │ ┌─┼───┼─┐ │     │
    │   │ │ │   │ │ │     │
    │   │ │A∩B│   │ │     │
    │   │ └─┼───┼─┘ │     │
    │   └───┘   └───┘     │
    │                     │
    └─────────────────────┘

A ∪ B: Both circles
A ∩ B: Overlapping region
A − B: Left circle only (no overlap)
A': Everything outside circle A

5. Power Sets

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

Example: If A = {1, 2}, then: P(A) = {∅, {1}, {2}, {1, 2}}

Key property: |P(A)| = 2^|A|

Proof intuition: For each element, we choose to include it or not (2 choices per element).

6. Cartesian Product

The Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.

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

Example:

  • A = {1, 2}, B = {a, b}
  • A × B = {(1, a), (1, b), (2, a), (2, b)}

Properties:

  • |A × B| = |A| × |B|
  • A × B ≠ B × A (unless A = B or one is empty)
  • A × ∅ = ∅

Multiple sets: A × B × C = {(a, b, c) | a ∈ A, b ∈ B, c ∈ C}

7. Set Identities

These identities are analogous to logical equivalences.

Identity Laws

  • A ∪ ∅ = A
  • A ∩ U = A

Domination Laws

  • A ∪ U = U
  • A ∩ ∅ = ∅

Idempotent Laws

  • A ∪ A = A
  • A ∩ A = A

Complement Laws

  • A ∪ A' = U
  • A ∩ A' = ∅
  • (A')' = A

Commutative Laws

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

Associative Laws

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

Distributive Laws

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

De Morgan's Laws

  • (A ∪ B)' = A' ∩ B'
  • (A ∩ B)' = A' ∪ B'

Absorption Laws

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

8. Application to Computer Science

Sets in Python

# Creating sets
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8}
empty = set()  # Note: {} creates an empty dict, not set

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

# Set operations
print(A | B)       # Union: {1, 2, 3, 4, 5, 6, 7, 8}
print(A & B)       # Intersection: {4, 5}
print(A - B)       # Difference: {1, 2, 3}
print(A ^ B)       # Symmetric difference: {1, 2, 3, 6, 7, 8}

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

# Cardinality
print(len(A))      # 5

# Set comprehension
squares = {x**2 for x in range(1, 6)}  # {1, 4, 9, 16, 25}

Sets in Databases (SQL)

-- Union (combine rows from two queries)
SELECT name FROM employees
UNION
SELECT name FROM contractors;

-- Intersection (common rows)
SELECT name FROM employees
INTERSECT
SELECT name FROM managers;

-- Difference (in first but not second)
SELECT name FROM employees
EXCEPT
SELECT name FROM terminated;

Type Systems

In programming, types can be thought of as sets of values:

  • int is the set of all integers
  • string is the set of all strings
  • Union types: int | string is the union of integers and strings
// TypeScript union types
type StringOrNumber = string | number;

// Intersection types
type Employee = Person & HasSalary;

Database Relationships

Cartesian products model relationships:

  • Students × Courses = all possible (student, course) pairs
  • The actual enrollment is a subset of this Cartesian product

9. Counting with Sets

Inclusion-Exclusion Principle

For two sets: |A ∪ B| = |A| + |B| − |A ∩ B|

For three sets: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

Example: In a class of 30 students:

  • 18 take Math
  • 15 take Physics
  • 10 take both

How many take at least one? |M ∪ P| = 18 + 15 − 10 = 23 students

Exercises

Basic

  1. Let A = {1, 2, 3, 4} and B = {3, 4, 5, 6}. Find:

    • A ∪ B
    • A ∩ B
    • A − B
    • B − A
    • A △ B

  2. Write these sets in roster notation:

    • {x ∈ ℤ | −2 ≤ x ≤ 3}
    • {x | x is a vowel}
    • {2ⁿ | n ∈ ℕ and n ≤ 4}

  3. Find P({a, b, c}). What is its cardinality?

Intermediate

  1. Prove: A ⊆ B if and only if A ∩ B = A

  2. Prove: (A ∩ B) ∪ (A ∩ B') = A

  3. In a survey of 100 people:

    • 60 like coffee
    • 50 like tea
    • 30 like both How many like neither?

Advanced

  1. Prove De Morgan's Law: (A ∪ B)' = A' ∩ B'

  2. For finite sets A and B, prove: |A × B| = |A| × |B|

  3. Prove that for any set A: |P(A)| = 2^|A|

Summary

  • Sets are unordered collections of distinct elements
  • Key operations: union (∪), intersection (∩), difference (−), complement (')
  • Power set P(A) contains all subsets; |P(A)| = 2^|A|
  • Cartesian product creates ordered pairs from two sets
  • Set identities mirror logical equivalences
  • Inclusion-exclusion counts elements in unions

Next Reading

Relations and Functions →