next up previous
Next: Congruence modulo n Up: NOTES ON RELATIONS Previous: Relations on a set

Equivalence relations

A relation tex2html_wrap_inline168 on A is an equivalence relation if it is reflexive, symmetric and transitive. An example of such is equality on a set. One might think of equivalence as a way to glob together elements that can be considered the same relative to a property. That is elements become indistinguishable relative to the relation. For example in arithmetic we don't think twice about 1/2 and 2/4 as having the same value but they are different objects. In geometry, similarity of triangles is an equivalence relation. A right angled triangle with legs of length 3 and 4 and hypotenuse of length 5 is not the same as one with lengths 6, 8 and 10. Yet, we think of them as equivalent because the ratios of the corresponding sides are the same.

For each tex2html_wrap_inline124 , we define the equivalency class containing a to be the set of those elements which are equivalent to a. We denote this set by [a] although you should be aware that there is no standard notation for this. Some authors use tex2html_wrap_inline240 , <a> and so on. The equivalence classes have some interesting properties. First, no equivalence class is empty since tex2html_wrap_inline244 . Two equivalence classes are either equal or disjoint. In fact, a and b are equivalent if and only if [a] = [b]. Each element of A belongs to some equivalence class ( in fact tex2html_wrap_inline244 ). The union of all the equivalence classes is A. We say that the equivalence classes partition A. A partition of A is a collection of non empty disjoint subsets of A and whose union is A. Thus the equivalence classes of a relation are a partition. Each equivalence relation on a set partitions the set into its equivalence classes but also for each partition of the set there is an equivalence relation whose equivalence classes are the sets in the partition. As an example, if tex2html_wrap_inline132 one partition is tex2html_wrap_inline258 . Consequently, there is an equivalence relation on A whose equivalence classes are these two subsets.

One problem is how should we refer to the equivalence classes? As we noted above [a] = [b] whenever a and b are equivalent. What we do is choose one and only one element of each equivalence class to represent the class. That element is called a class representative. The set of representatives is called the set of equivalence class representatives. There are usually many such ways to construct this set of representatives.

If tex2html_wrap_inline168 is an equivalence relation on A then the factor set denoted by tex2html_wrap_inline270 is the set consisting of the equivalence classes of tex2html_wrap_inline168 . For the example we gave above, our equivalence classes are [1] and [3]. Thus the factor set is {[1], [3]}. We have chosen 1 to represent the equivalence class {1,2} and (no choice) 3 to represent the equivalence class {3}. Thus the set of class representatives is {1,3}. Note the similarity with the factor set. The only difference is that the elements of the factor set have [ and ] around the number (and of course are subsets of A whereas the things in the set of class representatives are elements of A). Because of this, we often abuse notation and write the set of class representatives for the factor set, letting the context make it clear how we are using a class representative.


next up previous
Next: Congruence modulo n Up: NOTES ON RELATIONS Previous: Relations on a set

Peter Williams
Wed Nov 20 00:52:35 PST 1996