Session 6: Sets, Relations, Orders, Closures

Overview

Sets and relations: proving set identities as quantifier statements, classifying relations, and defining closures three different ways.

Lecturer

Omar Sinno (ECE)

Session Information

Core Concepts

  • Operations on sets, power sets, Cartesian products, and indexed families
  • Proving set identities as ∀-proofs
  • Relations as subsets of A × B; compositions and inverses
  • Properties: symmetry, antisymmetry, transitivity, and reflexivity
  • Equivalence relations, partitions, and quotients
  • Partial and total orders; Hasse diagrams
  • Closures: reflexive, transitive, and the reflexive-transitive closure R*, defined in three ways (smallest relation with the property; union of powers; inductively, by rules)
  • Russell’s paradox

Slides

Session 6 Slides: Download PDF

Readings

Exercises & Extra Steps

  • Practice (not collected): prove (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ by element chasing
  • Practice (not collected): show that the transitive closure of R equals ⋃_{n≥1} Rⁿ
  • Problem Set 2 released today — due on paper at the start of S8 (Thu 1 Oct)

Questions? Reach out on the course WhatsApp!