🔗 Module 2: Binary Relations

Duration: Weeks 3-7

📚 Core Topics

Properties of Relations

Reflexive & Irreflexive: Self-relationships
Symmetric, Antisymmetric & Asymmetric: Bidirectional behavior
Transitive: Chain relationships
Composition & Closures: Building new relations

Equivalence Relations (Weeks 3-4)

Definition and properties
Equivalence classes
Partitions and quotient sets
Fundamental theorem: Equivalences <-> Partitions

Order Relations (Weeks 4-5)

Partial Orders (Posets): ≤ relation
Linear/Total Orders: Complete ordering
Well-orderings: Every subset has minimum
Hasse Diagrams: Visual representation
Elements: Maximal/minimal, greatest/least
Structures: Chains and antichains
Dilworth’s Theorem: Chain decomposition

Functions (Week 5)

Functions as special relations
Components: Domain, codomain, range, image, preimage
Types:
- Injective (one-to-one)
- Surjective (onto)
- Bijective: Both injective and surjective
Composition and inverses

Lattices (Week 7)

Upper and lower bounds
Suprema and infima
Complete lattices
Modular and distributive lattices
Boolean algebras as lattices

🔑 Key Definitions

Relation Type	Properties	Example
Equivalence	Reflexive + Symmetric + Transitive	Equality, Congruence
Partial Order	Reflexive + Antisymmetric + Transitive	Divisibility, Subset
Total Order	Partial Order + Any two comparable	≤ on ℝ
Function	Each input maps to exactly one output	f: ℕ → ℕ, f(n) = n²

💡 Applications

Real-world uses:

🗄️ Database design and normalization
🔍 Program analysis and verification
📅 Scheduling and task ordering
🔐 Cryptographic hash functions
🎯 Algorithm optimization

✅ Learning Outcomes

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

✓ Determine and prove properties of relations
✓ Find equivalence classes and construct quotient sets
✓ Draw and interpret Hasse diagrams for partial orders
✓ Prove functions are injective/surjective/bijective
✓ Compose functions and find inverses
✓ Apply pigeonhole principle to solve counting problems