A relation that is reflexive, symmetric and transitive is an equivalence relation. It divides its set into equivalence classes: groups that do not overlap and together contain every element.
A relation that is reflexive, symmetric and transitive is called an equivalence relation.
Equality is the basic example. a = a for every a (reflexive). If a = b then b = a (symmetric). If a = b and b = c then a = c (transitive). An equivalence relation is a kind of equality in one chosen respect: two elements are related when they are the same in that respect, even if they differ in others.
Congruence of triangles is an example. Two triangles are congruent if each side of one equals the matching side of the other and each angle equals the matching angle. Congruent triangles can differ in position but are the same in shape and size.
Show that “is congruent to”, on the set of all triangles in a plane, is an equivalence relation.
Reflexive: each side and angle of a triangle T equals itself, so T is congruent to T.
Symmetric: if the sides and angles of T₁ equal those of T₂, then those of T₂ equal those of T₁, because equality of lengths and angles is symmetric. So T₁ congruent to T₂ implies T₂ congruent to T₁.
Transitive: if the sides and angles of T₁ equal those of T₂, and those of T₂ equal those of T₃, then those of T₁ equal those of T₃. So T₁ is congruent to T₃.
All three hold, so congruence is an equivalence relation. Each property was inherited from equality of the side lengths and angles.
For an equivalence relation R on A, the equivalence class of an element a, written [a], is the set of all elements of A related to a:
[a] = { x ∈ A : x R a }
The three properties give the classes three features:
So the classes cover all of A and do not overlap. A division of a set into such groups is called a partition.
On the integers, define a R b if a − b is divisible by 2. Then a and b are related exactly when they leave the same remainder on division by 2. This relation is reflexive (a − a = 0 is divisible by 2), symmetric (if 2 divides a − b, it divides b − a) and transitive (if 2 divides a − b and b − c, it divides their sum a − c).
Division by 2 leaves remainder 0 or 1, so there are two classes. [0] is the set of even integers. [1] is the set of odd integers. Every integer is in exactly one of them, and no even integer is related to an odd one.
With “a − b is divisible by 3”, the possible remainders are 0, 1 and 2, giving three classes: [0] = {…, −3, 0, 3, 6, …}, [1] = {…, −2, 1, 4, 7, …} and [2] = {…, −1, 2, 5, 8, …}. In general, “a − b is divisible by n” gives n classes, one for each remainder 0, 1, …, n − 1.
A partition. The classes of an equivalence relation cover the whole set and do not overlap. Shown: the three classes of “same remainder on division by 3”.
On A = {1, 2, 3, 4, 5, 6, 7}, the relation “a R b if a and b are both odd or both even” is an equivalence relation. What are its classes?
The odd elements, 1, 3, 5 and 7, are all related to one another. They form the class {1, 3, 5, 7}.
The even elements, 2, 4 and 6, are all related to one another. They form the class {2, 4, 6}.
Every element of A is in exactly one class, and together the classes contain all seven elements. No odd element is related to an even one.
1An equivalence relation is one that is…
2Why is equality the basic example of an equivalence relation?
3The set of all elements related to a, written [a], is the equivalence ____ of a.
4The equivalence classes of an equivalence relation on a set…
5For “a R b if a − b is divisible by 2” on the integers, the classes are…
6For “a R b if a − b is divisible by 3” on the integers, how many classes are there?
Next: functions that are one-one, onto, or both.
Noescio