Make your own free website on Tripod.com
The set of integers. If a congruent b(mod n) and c congruent d(mod n), then (a+c) congruent (b+d)(mod n) and ac congruent bd(mod n).

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 congruent a(mod n).

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

3. If a congruent b(mod n) and b congruent c(mod n), then a congruent 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 union 1 union...union n-1.

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

i intersect j = empty set   (0 < i < j < n-1, i not equal 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 collection of subsets of S such that

a.  partition

b. If A and B are distinct elements of collection, then A intersect B = empty set.

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 collection if they lie in the same set of collection. In this case, we will write x ~collection y. Note that properties (1), (2), and (3) carry over to our more general notion of congruence. Namely, we have

1collection. x ~collection x  for all x element of S.

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

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

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

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

If R is a relation on S and if (x,y) element of 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 collection on a set S determines a relation Rcollection on S, the relation

Rcollection = {(x,y) element of S cross S | x ~C y}.

In this case x ~Rcollection y if and only if x ~collection y. Such a relation has very special properties, 1collection-3collection. Lest the reader think that 1collection-3collection 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 1collection is violated. Moreover, 3 ~R 1, but it is not true that 1 ~R 3, so 2collection is violated. Finally, 3 ~R 1 and 1 ~R 2, but it is not true that 3 ~R 2, so that 3collection is violated. A relation satisfying 1collection-3collection 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 element of S, x ~R x.

If x,y element of S and x ~R y, then y ~R x

ER2. If x,y element of S and x ~R y, then y ~R x.

If x,y,z element of S and x ~R y, y ~R z, then x ~R z.

ER3. If x,y,z element of 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 collection on S such that R is the equivalence relation associated with collection. For each x element of S, let

Ax = {y element of S | x ~R y},

and set

collection = {Ax | x element of S},

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

1. collection is a partition on S.

2. R is the equivalence relation associated with collection.

It is clear that 2 holds provided 1 does. Thus it suffices to prove 1. Since x ~R x, we see that x element of Ax, so that

relation union

Assume that

Ax intersect Ay not equal empty set

We must show that Ax = Ay. Assume that z element of Ax intersect Ay, and we let w element of Ax. Then

x ~R z,   y ~R z,   x ~R w.

Therefore, by ER2,

x ~R z,   z ~R y,   w ~R x.

so that by ER3 and ER2,

w ~R x,   x ~R y.

which implies that w ~R y, by ER3. Thus y ~R w, by ER2, and we have shown that if w element of Ax, then w element of Ay. Therefore, Ax subset ofAy. Interchanging x and y we see that Ay subset of Ax. Therefore, Ax = Ay.

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 collection is its associated partition, then the sets contained in collection 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 not equal 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 not equal 0, and let us define an equivalence relation ~ on S by

a/b ~ c/d equivalent 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

{a/b, 2a/2b, (-1)a/(-1)b, 6a/6b, ...},

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 element of 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 element of Z, and a ~ b, c ~ d, then a congruent b(mod n), c congruent d(mod n), so that a + c congruent b + d(mod n), a · c congruent b · d(mod n) by Proposition 2 part(4). Thus, a + c ~ b + d and a · c congruent b · d.

If A is a set and ~ is an equivalence relation on A, let A/~ = {Ax | x element of 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:

(2)
Ax *' Ay = Ax*y.

Please note that in order for (2) to define a binary operation on A/~, we must show that the "product" of Ax and Ay depends only of Ax and Ay and not on the choice of x in Ax and y in Ay - that is we must show that Ax = Ax', Ay = Ay', then we have Ax*'Ay = Ax'*'Ay'. But, if Ax = Ax', then x ~ x'. Similarly, if Ay = Ay', then y ~ y'. Thus, since * is compatible with ~, we have x*y ~ x'*y', and therefore Ax*y = Ax'*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.