🔗 Test 2 – Binary Relations

📅 Test Details

📚 Topics Covered

• Relation properties (reflexive, symmetric, transitive, antisymmetric)
• Equivalence relations and partitions
• Order relations and Hasse diagrams
• Functions (injective, surjective, bijective)
• Composition of functions
• Cardinality (finite, countable, uncountable)

🎯 Sample Problem Types

• Properties: Determine which properties a given relation satisfies
• Equivalence Classes: Find equivalence classes for given relation
• Hasse Diagrams: Draw diagram for partial order
• Functions: Prove given function is bijective
• Composition: Compute composition of given functions
• Cardinality: Show rationals are countable using diagonalization

📖 Preparation Guide

Review Materials

1. Lecture Notes: Module 2 (Binary Relations)
2. Homework: HW 2
3. Textbook: Kenneth Rosen

Practice Problems

• Relations: Check properties for 10+ different relations
• Equivalence: Find equivalence classes for modular arithmetic
• Hasse Diagrams: Draw for divisibility, subset, lexicographic order
• Functions: Prove injectivity/surjectivity for various \( f : A \to B \)
• Composition: Compute compositions and verify associativity
• Cardinality: Review proofs that \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\) are countable; \(\mathbb{R}\) is uncountable

Common Pitfalls

⚠️ Watch Out!

• Antisymmetric is NOT the same as “not symmetric” (check definition!)
• In Hasse diagrams, don’t draw transitive edges
• Composition order: \( f \circ g \) means “\(f\) after \(g\)”
• Equivalence classes must partition the set (disjoint and cover all)
• Injection and surjection are different concepts!

💡 Pro Tips

• Test systematically – for properties, check all pairs methodically
• Use counterexamples – one pair can disprove a property
• Hasse diagrams – start with minimal/maximal elements
• Function proofs – use “suppose \(f(a) = f(b)\)” for injection
• Cardinality – know diagonalization and zig-zag arguments
• Partition check – equivalence classes should be disjoint and exhaustive