Next: Posets Up: Binary relations Previous: Binary relations between elements   Contents

# Equivalence relations

Definition 4.3.1   The relation on is an equivalence relation if it is reflexive, symmetric and transitive.

We often denote these properties by RST''; note that R'' (for reflexivity) concerns single elements, S'' (for symmetry) concerns pairs of elements, and T'' (for transitivity) concerns triples of elements. These are nice'' properties designed to make behave something like , with respect to some specific property of the elements of the set.

Example 4.3.2   Consider the set of all integers and the relation on defined as follows:

This relation is an equivalence relation on :
(i)
R: , thus .
(ii)
S: , i.e .
(iii)
T:

It follows that, i.e. .

Example 4.3.3   The binary relation given in Example 2.6 is an equivalence relation.

Definition 4.3.4   If is an equivalence relation on the set and , then

is called the equivalence class of .

Example 4.3.5   In Example 2.6, each possible eye color determines an equivalence class.

Definition 4.3.6   Let be a set. A collection of non empty subsets of form a partition of if the following conditions hold:
(i)
.
(ii)
If , then .

For example, the set of odd integers and the set of even integers form a partition of .

Theorem 4.3.7   If is an equivalence relation then the equivalence classes form a partition of .

Proof.
(i)
If then , so the classes cover all of .
(ii)
If then . Now and . Thus and . If then so and thus . We can similarly show that and thus .

The converse of this is true: if we have a partition of we can define an equivalence relation on by iff and are in the same part.

Remark 4.3.8 (For algebraists only)   An application of this is the proof of Lagrange's Theorem. The idea is to show that being in the same (left/right) coset is an equivalence relation.

Definition 4.3.9   Given an equivalence relation on , the set of all equivalence classes is called the quotient set and is denoted by .

Example 4.3.10   On the set of all the real numbers we define the following relation:

Th relation is an equivalence relation on (the proof is very similar to the proof in example 3.11). The equivalence class of the real number is the set , and any equivalence class contains a single element in the interval . Thus the unit circle in the plane is graphical representation of the quotient set: every point on the circle determines a single angle with the positive semi--axis, i.e. a single element of .

Example 4.3.11 (Congruences in )   This example is very important, both in Algebra and in Number Theory. Let be a positive integer. We define a binary relation in , called congruence modulo as follows:

Congruence modulo is an equivalence relation on :
• R: For any integer , we have:

i.e. .
• S: For any integers and , we have:

It follows that , thus .
• T: For any integers , and , we have:

It follows that , i.e. .
Let us describe the equivalence classes for various values of the positive integer :
1. If , we have:

i.e. every integer is congruent to every integer modulo . There is only one equivalence class modulo (therefore this congruence is not so interesting!).
2. If , there are two equivalence classes: the one contains all the even numbers, the other one contains all the odd numbers.
3. If , there are three equivalence classes, namely:

These examples are particular cases of a general result:

Theorem 4.3.12   Let be a positive integer. There are exactly congruence classes of integers modulo .

Proof. Let us use the Euclidean Division (v.i. Proposition 2.18 in Chapter 6): for any , there exists a unique pair , where , and . The integer is called the quotient and is the remainder. We have: , i.e. . By transitivity, two integers are congruent modulo if, and only if, they have the same remainder in division by . Therefore, the equivalence classes are completely determined by the integers verifying the double inequality , i.e. there are exactly equivalence classes.

Returning to a general relation , for each we define

 there is a path of length at from to

and , the transitive closure of . is defined as .

Next: Posets Up: Binary relations Previous: Binary relations between elements   Contents
root 2002-06-10