1.3 Equivalence Relations
There are many ways to compare elements of a set other than to say two elements are equal
or the same. For example, in the set of people let two people be equivalent if they have the
same weight. This would not be saying they were the same person, just that they weighed the
same. Often such relations involve considering one characteristic of the elements of a set and
then saying the two elements are equivalent if they are the same as far as the given
characteristic is concerned.
Definition 1.3.1 Let S be a set. ∼ is an equivalence relation on S if it satisfies
the following axioms.
- x ∼ x for all x ∈ S. (Reflexive)
- If x ∼ y then y ∼ x. (Symmetric)
- If x ∼ y and y ∼ z, then x ∼ z. (Transitive)
denotes the set of all elements of S which are equivalent
to x and
is called the equivalence class determined by x or just the equivalence class
With the above definition one can prove the following simple theorem.
Theorem 1.3.3 Let ∼ be an equivalence class defined on a set, S and let ℋ
denote the set of equivalence classes. Then if
are two of these equivalence
classes, either x ∼ y and
or it is not true that x ∼ y and