Module 2: Binary Relations
Duration: Weeks 3-7
Core Topics
Properties of Relations
- Reflexive, irreflexive
- Symmetric, antisymmetric, asymmetric
- Transitive
- Composition and closures
Equivalence Relations (Weeks 3-4)
- Definition and properties
- Equivalence classes
- Partitions and quotient sets
- Fundamental theorem: equivalence ↔ partition
Order Relations (Weeks 4-5)
- Partial orders (posets)
- Linear (total) orders
- Well-orderings
- Hasse diagrams
- Maximal/minimal, greatest/least elements
- Chains and antichains
- Dilworth’s theorem
Functions (Week 5)
- Functions as special relations
- Domain, codomain, range, image, preimage
- Injective (one-to-one)
- Surjective (onto)
- Bijective (one-to-one correspondence)
- Composition and inverses
- Pigeonhole principle
Lattices (Week 7)
- Meets (∧) and joins (∨)
- Complete lattices
- Modular and distributive lattices
- Boolean algebras as lattices
Key Concepts
Equivalence Relation: Reflexive + Symmetric + Transitive
Partial Order: Reflexive + Antisymmetric + Transitive
Function: Relation where each input has exactly one output
Bijection: Function that is both injective and surjective
Applications
- Database design and normalization
- Program analysis and verification
- Scheduling problems
- Cryptography
What You’ll Be Able To Do
- Determine properties of given relations
- Find equivalence classes and quotient sets
- Draw and interpret Hasse diagrams
- Prove functions are injective/surjective/bijective
- Compose functions and find inverses
- Apply pigeonhole principle to counting problems