Sets, Relations & Functions

The language of collections and mappings. Learn set notation, operations (union, intersection, difference, complement), Venn diagrams, power sets and Cartesian products, relations and their properties (reflexive, symmetric, transitive), equivalence relations and partial orders, and injective, surjective and bijective functions.

Databases are sets of records, relations model 'depends on' in build systems, equivalence classes group identical parts, and bijections ensure encodings can be decoded.

An analogy

A set is a bag of distinct items; a relation is a list of pairs saying which items are connected; a function is a rule that sends every item to exactly one partner.

Set operations

Venn diagrams visualise unions and intersections. De Morgan's laws: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ. Sets have no duplicates and no order.

Relations

A relation on A is a subset of A × A. Equivalence relations (reflexive, symmetric, transitive) partition sets into classes (e.g. congruence mod n). Partial orders (reflexive, antisymmetric, transitive) model precedence — task scheduling, dependency graphs.

Functions

Injective (one-to-one) functions lose no information; surjective (onto) cover the codomain; bijections are invertible. Hash functions are deliberately not injective (collisions).

Cardinality

Finite sets are compared by counting; infinite sets by bijections — integers and rationals are countable; reals are not (Cantor's diagonal argument).

Formulas

• Inclusion–exclusion (2 sets): |A ∪ B| = |A| + |B| − |A ∩ B|
• Sizes: |A × B| = |A||B|; |𝒫(A)| = 2^|A|
• Relation properties: Reflexive aRa; symmetric aRb ⇒ bRa; transitive aRb ∧ bRc ⇒ aRc
• Function types: Injective: f(a) = f(b) ⇒ a = b; surjective: every y hit; bijective: both

Worked example: Inclusion–exclusion

Given: Integers 1–1000 divisible by 3 or 5

Find: Count.

• ⌊1000/3⌋ = 333, ⌊1000/5⌋ = 200, ⌊1000/15⌋ = 66
• 333 + 200 − 66

Answer: 467

Worked example: Equivalence classes

Given: a ~ b if a ≡ b (mod 3) on ℤ

Find: Classes.

• Reflexive, symmetric, transitive ✓
• Classes: remainders 0, 1, 2

Answer: Three classes [0], [1], [2]

Common mistakes

• Wrong: Adding overlapping set sizes directly. — Right: Subtract intersections (inclusion–exclusion).
• Wrong: Assuming every function has an inverse. — Right: Only bijections are invertible.

Applications

• Databases: SQL joins and set operations.
• Build systems: Dependency relations and partial orders.
• Coding & hashing: Injective encodings, collision analysis.

Key takeaways

• Set operations and De Morgan.
• Inclusion–exclusion for counting unions.
• Equivalence relations and partial orders.
• Injective, surjective, bijective.

Going further

• Relational algebra: Theory behind SQL.
• Lattices: Partial orders with meets and joins.
• Countability: Cantor's diagonal argument.