Session 7B
Equivalence relations and classes
45-75 min - work through lesson notes, practice, and the MCQ check.
In progress
Account sync
Sign in to keep this session synced across devices.
Account sync disabled
Add Supabase environment variables to enable account sync. Progress is saved locally in this browser for now.
Session tips
- Finish the MCQ before marking complete.
- Check the answer outlines after trying on paper.
- Mark complete to update your certificate progress.
Lesson notes
- An equivalence relation is a relation that is reflexive, symmetric, and transitive. Equivalence relations capture the idea of "same type" under some criterion, like "same remainder mod n." When a relation is an equivalence relation, it partitions the set into equivalence classes, where each class consists of all elements related to a given element. For example, under "same parity," there are exactly two classes: the evens and the odds. Each element belongs to exactly one class.
- Equivalence classes matter because they let you simplify a messy set into a smaller set of categories. Modular arithmetic is built on this: the equivalence classes mod n are the residue classes [0], [1], ..., [n-1]. Proving something is an equivalence relation is usually straightforward, but the deeper understanding is recognizing that once you have equivalence classes, you can work with representatives and avoid repeating the same argument for infinitely many elements.
Practice
- 1Describe the equivalence class of 3 under 'same parity'.
- 2Show congruence mod n is an equivalence relation.
MCQ
The equivalence class of 3 under 'same parity' is: