Equivalence Relations and Partitions
An equivalence relation is a binary relation that is reflexive, symmetric, and transitive.
Summary
An equivalence relation is a binary relation that is reflexive, symmetric, and transitive. It groups elements into equivalence classes, with each element belonging to exactly one class.
| Structure | Description |
|---|---|
| Equivalence relation | Specifies which elements count as equivalent. |
| Partition | Divides a set into nonempty, pairwise disjoint subsets that cover the entire set. |
| Quotient set | Collects the distinct equivalence classes as its elements. |
For a relation on , the equivalence class of is . Two classes satisfy . The distinct classes form a partition. Conversely, any partition induces an equivalence relation by relating elements exactly when they belong to the same block.
🧠 Key Concepts
- Reflexivity
- Symmetry
- Transitivity
- Equivalence Classes
- Partition Blocks
- Class Equality
- Quotient Sets
- Canonical Representatives
🧠 Quick Check
See what you remember from the summary.
Which combination of properties defines an equivalence relation?
🧠 Flashcards Preview
Tap a card to reveal the definition.
Ready to quiz yourself?
Test what you remember with a full practice quiz on this note. Create a free account and start in seconds.
Full Notes
Read the original note content before deciding whether to save or study from it.
Equivalence Relations and Partitions
📘 Overview An equivalence relation groups elements into nonempty, disjoint classes that together contain every element of the underlying set. Equivalence relations and partitions describe the same structure: each uniquely determines the other.
🧠 Key Idea An equivalence relation formalizes when two elements count as equivalent. Its equivalence classes form a partition, so each element belongs to exactly one class.
⚔️ Core Details: - Reflexivity: for every , where
More ways to study when you copy this note
Copy this note into your library to unlock focused practice sessions and long-term review.
Answer all questions first, then see feedback at the end — the way real exams work.
Focuses each session on what you got wrong, not what you already know.
Full timed exam with all questions, no pausing, and results at the end. Built for board exam prep.
Part of 🌱 BSCS Year 1 — Computing & College Foundations
Browse this Review Set →More Computer Engineering notes
See all →More in Discrete Mathematics
See all →More from NoteLib
Browse NoteLib's public notes →Copy this note to your library and get the full Study Pack instantly — summary, key concepts, and practice quiz included.