Module 1: Set Theory

Duration: Weeks 1-2 + Week 6

Core Topics

Weeks 1-2: Foundations

• Set operations (∪, ∩, , ⊕, complement)
• Power sets and Boolean algebra of sets
• Venn diagrams
• Cartesian products
• Russell’s paradox
• Zermelo-Fraenkel axioms (ZFC)
• Axiom of choice

Week 6: Cardinality

• Finite vs infinite sets
• Countable and uncountable sets
• Pairing functions and encodings
• Cantor’s diagonal argument
• Cantor’s theorem: |A| < |𝒫(A)|
• Schroeder-Bernstein theorem
• Hilbert’s hotel paradox

Key Concepts

Set Operations: Union, intersection, difference, symmetric difference, complement

Power Set: 𝒫(A) = set of all subsets of A. If |A| = n, then |𝒫(A)| = 2ⁿ

Cardinality:

• Finite: |A| = n for some n ∈ ℕ
• Countable: |A| = |ℕ| (e.g., integers, rationals)
• Uncountable: |A| > |ℕ| (e.g., real numbers)

Applications

• Database theory and relational algebra
• Probability theory foundations
• Formal language theory

What You’ll Be Able To Do

• Prove set identities using element arguments or algebraic laws
• Construct Venn diagrams for complex expressions
• Determine cardinality of finite and infinite sets
• Prove sets are countable or uncountable
• Apply Cantor’s diagonal argument