Equivalence relations
A reflexive, symmetric and transitive relation: equivalence classes, representatives, the quotient set and the associated partition, with congruence modulo n, same square or same number of 1 bits.
- 26 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
Equivalence relation: what is it?
Show the answer
A relation that is reflexive, symmetric and transitive at once: it groups the elements regarded as “alike” for a given criterion.
All three properties are needed. “Being the same age” is one; “being friends with” is not, since friendship is not transitive.
On ℤ, x R y means |x − y| ≤ 1. Which property of an equivalence does it lack?
- Transitivity
- Reflexivity
- Symmetry
- Antisymmetry
Show the answer
Transitivity
1 R 2 and 2 R 3, but |1 − 3| = 2: 1 is not related to 3. The relation is reflexive and symmetric; antisymmetry is not required of an equivalence anyway.
An equivalence relation is …, … and ….
Show the answer
An equivalence relation is reflexive, symmetric and transitive.
If any of the three is missing, the classes no longer form a partition: elements would land in several groups at once, or in none.
Equivalence class: what is it?
Show the answer
The set of all elements related to a given element x by the relation. Two elements of the same class are related to each other.
Two classes are either identical or disjoint: an element common to two classes would merge them by transitivity.