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
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