applet-magic.com
Thayer Watkins
Silicon Valley
USA

 Equivalence Relations and Equivalence Classes

An equivalence relation is a quite simple concept. Let S be a set. A relation R tells for any two members, say x and y, of S whether x is in that relation to y. For example, if S is a set of numbers one relation is ≤. For any two numbers x and y one can determine if x≤y or not. Another relation of integers is divisor of, usually denoted as |. Thus 2|6 says 2 is a divisor of 6.

Abstractly considered, any relation on the set S is a function from the set of ordered pairs from S, called the Cartesian product S×S, to the set {true, false}. The relation is usually identified with the pairs such that the function value equals true.

An equivalence relation R is a special type of relation that satisfies three conditions:

• Reflexivity: xRx
• Symmetry: If xRy then yRx
• Transitivity: If xRy and yRz then xRz

The set of elements of S that are equivalent to each other is called an equivalence class. The equivalence relation partitions the set S into muturally exclusive equivalence classes.

The power of the concept of equivalence class is that operations can be defined on the equivalence classes using representatives from each equivalence class. In order for these operations to be well defined it is necessary that the results of the operations be independent of the class representatives selected.

For fractions, (a/b) is equivalent to (c/d) if one can be represented in the form in which its components are a constant multiple of the components of the other, say (c/d)=(ka/kb). This is equivalent to (a/b) and (c/d) being equal if ad-bc=0. Thus the equivalence classes are such as

#### {1/2, 2/4, 3/6, … } {2/3, 4/6, 6/9, … }

A rational number is then an equivalence class. It is only representated by its lowest or reduced form. The equivalence class could equally well be represented by any other member.