Equivalence Relations

In the section on congruences we introduced the notion of congruence of integers modulo n, and we proved the following basic properties of congruence:

1. a a(mod n).

2. If a b(mod n), then b a(mod n).

3. If a b(mod n) and b c(mod n), then a c(mod n).

Moreover, we showed that the integers are distributed among the residue classes {0, 1, ..., n-1}, which satisfy the following properties:

1'. Every integer x belongs to one of the residue classes {0,1,...,n-1}, so that

Z = 0 1 ... n-1.

2'. No integer belongs to two of the residue classes {0,1,...,n-1}, so that

i j =   (0 < i < j < n-1, i l).

Let us abstract from this data two very important notions - that of partition and equivalence relation.

Let S be a set. A partition of S is a collection of subsets of S such that

a.  

b. If A and B are distinct elements of , then A B = .

For example, 1' and 2 ' assert that {0, 1, ..., n-1} is a partition of Z. Thus, the notion of a partition may be viewed as a generalization of the notion of distributing the integers in residue classes modulo n. By analogy with the example of congruences, let us say that two elements x and y of S are congruent with respect to the partition if they lie in the same set of . In this case, we will write x ~ y. Note that properties (1), (2), and (3) carry over to our more general notion of congruence. Namely, we have

1. x ~ x  for all x S.

2. If x ~ y, then y ~ x.

3. If x ~ y and y ~ z, then x ~ z.

The above example suggests the following definition: Let S be a set. Then a relation R on S is a subset of S S. For example, if S = {1, 2, 3}, then a relation R is given by

R = {(1,1), (1,2), (2,1),( 3,1)} S S.

If R is a relation on S and if (x,y) R, then we say that x is related to y with respect to R, and we often write x ~_R y. Note that a partition on a set S determines a relation R on S, the relation

R = {(x,y) S S | x ~_C y}.

In this case x ~_R y if and only if x ~ y. Such a relation has very special properties, 1-3. Lest the reader think that 1-3 are satisfied by any relationship, we should examine closely the relation R, which is defined by (1). It is not true that 2 ~_R 2, so 1 is violated. Moreover, 3 ~_R 1, but it is not true that 1 ~_R 3, so 2 is violated. Finally, 3 ~_R 1 and 1 ~_R 2, but it is not true that 3 ~_R 2, so that 3 is violated. A relation satisfying 1-3 is called an equivalence relation. More precisely, if S is a set and R is a relation on S, then R is said to be an equivalence relation if the following properties hold:

ER1. For every x S, x ~_R x.

If x,y S and x ~_R y, then y ~_R x

ER2. If x,y S and x ~_R y, then y ~_R x.

If x,y,z S and x ~_R y, y ~_R z, then x ~_R z.

ER3. If x,y,z S and x ~_R y, y ~_R z, then x ~_R z.

The properties ER1-ER3 are called the reflexive, symmetric, and transitive laws, respectively. They completely characterize an equivalence relation, in the following sense: Suppose there is given a relation R on S which satisfies rules ER1-ER3. Then it is possible to associate R on a partition on S such that R is the equivalence relation associated with . For each x S, let

A_x = {y S | x ~_R y},

and set

= {A_x | x S},

(Note that A_x may be equal to A_y for x y, so some sets may be repeated in our description of C.) We claim that

1. is a partition on S.

2. R is the equivalence relation associated with .

It is clear that 2 holds provided 1 does. Thus it suffices to prove 1. Since x ~_R x, we see that x A_x, so that

Assume that

A_x A_y

We must show that A_x = A_y. Assume that z A_x A_y, and we let w A_x. Then

Therefore, by ER2,

so that by ER3 and ER2,

which implies that w ~_R y, by ER3. Thus y ~_R w, by ER2, and we have shown that if w A_x, then w A_y. Therefore, A_x A_y. Interchanging x and y we see that A_y A_x. Therefore, A_x = A_y.

Note: The reader should carefully master the relationship between a partition and an associated equivalence relation, since this idea will be used over and over later.

If ~ is an equivalence relation and is its associated partition, then the sets contained in are called equivalence classes with respect to ~. Two elements are equivalent with respect to ~ if and only if they belong to the same equivalence class.

Equivalence relations occur with surprising frequency in even the most innocent of contexts. For example, consider the rational numbers (or fractions). From our days in grade school, we are accustomed to thinking of a rational number as the quotient a/b of integers a and b (b 0). However, strictly speaking, this is not correct, since we do not regard the rational numbers 1/3, 2/6, 3/27 as different from one another. However, there is a simple way out of this logical difficulty. Let S denote the set of all quotients a/b, where a and b are integers, b 0, and let us define an equivalence relation ~ on S by

a/b ~ c/d ad - bc = 0.

It is easy to verify that ~ is an equivalence relation and that all the ratios a/b, 2a/2b, 3a/3b, etc., are equivalent to one another. Then a rational number can be defined to be an equivalence class belonging to ~. Roughly speaking a rational number is the "common value" of the ratios

Suppose that A is a set and ~ is an equivalence relation over A. Moreover, suppose that * is a binary operation on A. We will say that * is compatible with ~ if, whenever a ~ b, c ~ d (a,b,c,d A), we have a * c ~ b * d. For example, if A = Z, and ~ is the equivalence relation on Z defined by the partition {0,1,...,n-1}, then ~ is compatible with the binary operations of addition and multiplication. For indeed, if a,b,c,d Z, and a ~ b, c ~ d, then a b(mod n), c d(mod n), so that a + c b + d(mod n), a · c b · d(mod n) by Proposition 2 part(4). Thus, a + c ~ b + d and a · c b · d.

If A is a set and ~ is an equivalence relation on A, let A/~ = {A_x | x A} denote the set of equivalence classes of A with respect to ~. If * is a binary operation on A which is compatible with respect to ~, then we can define a binary operation called *' on A/~ as follows:

Please note that in order for (2) to define a binary operation on A/~, we must show that the "product" of A_x and A_y depends only of A_x and A_y and not on the choice of x in A_x and y in A_y - that is we must show that A_x = A_x', A_y = A_y', then we have A_x*'A_y = A_x'*'A_y'. But, if A_x = A_x', then x ~ x'. Similarly, if A_y = A_y', then y ~ y'. Thus, since * is compatible with ~, we have x*y ~ x'*y', and therefore A_x*y = A_x'*y', and thus we have shown that *' does, indeed, define a binary operation on the set of equivalence classes A/~.

In what follows, we will give many examples of equivalence relations on various algebraic structures (for example, groups, rings) and of binary operations compatible with these relations, so we will refrain from giving further examples at this point.