Past exam question: 2082 Chaitra (Regular), Q1(a)
Open in the Padhaiko appDefine equivalence and partial-equivalence relation.
Solution
Equivalence Relation Definition and Properties: A binary relation on a set is an equivalence relation if and only if it satisfies three fundamental properties for all :
- Reflexivity: .
- Symmetry: .
- Transitivity: .
Example: The relation of congruence modulo on the integers , defined by iff , is an equivalence relation because every number is congruent to itself, congruence is bidirectional, and modular differences chain transitively.
Partial-Equivalence Relation (PER) Definition: A binary relation on a set is a partial-equivalence relation (PER) if it is symmetric and transitive, but not necessarily reflexive:
- Symmetry: .
- Transitivity: .
For a partial-equivalence relation, an element is related to itself () if and only if there exists some such that . Consequently, forms an ordinary equivalence relation on the restricted domain .
Example: On , define . Here, is not related to itself, so reflexivity fails on , but symmetry and transitivity hold everywhere.
An equivalence relation is reflexive, symmetric, and transitive (e.g., congruence modulo ). A partial-equivalence relation (PER) is symmetric and transitive without requiring reflexivity for all elements of the underlying set.