Excerpted from Beachy/Blair, Abstract Algebra, 2nd Ed. © 1996

Forward to §2.3 | Back to §2.1 | Up | Table of Contents | About this document


§ 2.2 Equivalence Relations

 
Definition 2.2.1. Let S be a set. A subset R of S × S is called an equivalence relation on S if

(i) for all a in S, (a,a) belongs to R;

(ii) for all a,b in S, if (a,b) is in R then (b,a) is in R;

(iii) for all a,b,c in S, if (a,b) is in R and (b,c) is in R, then (a,c) is in R.
    We will write a ~ b to denote the fact that (a,b) is in R.

 
Rather than using the formal definition of an equivalence relation, given in terms of ordered pairs, we will usually use the following conditions.

Let S be a set. Then ~ defines an equivalence relation on S if and only if

(i) the reflexive law holds :
given any x in S, we always have x ~ x ;

(ii) the symmetric law holds :
given any x and y in S, if x ~ y , then y ~ x ;

(iii) the transitive law holds :
given any x, y and z in S, if x ~ y and y ~ z , then x ~ z .

 
Definition 2.2.2. Let ~ be an equivalence relation on the set S. For a given element a in S, we define the equivalence class of a to be the set of all elements of S that are equivalent to a.
We will use the notation [a]. In symbols,

[a] = { x in S | x ~ a }.

    The notation S/~ will be used for the collection of all equivalence classes of S under ~.

 
Example 2.2.2 (S/f) Let f : S -> T be any function. For x1, x2 in S we define

x1 ~ x2     if     f(x1) = f(x2).

Then for all x1, x2, x3 in S we have
    (i) f(x1) = f(x1);
    (ii) if f(x1) = f(x2), then f(x2) = f(x1);
    (iii) if f(x1) = f(x2) and f(x2) = f(x3), then f(x1) = f(x3).
This shows that we have defined an equivalence relation on the set S. The proof of this is easy because the equivalence relation is defined in terms of equality of the images f(x), and equality is the most elementary equivalence relation.
    The collection of all equivalence classes of S under ~ will be denoted by S/f.

 
Proposition 2.2.3. Let S be a set, and let ~ be an equivalence relation on S. Then each element of S belongs to exactly one of the equivalence classes of S determined by the relation ~.

 
Definition 2.2.4. Let S be any set. A family P of subsets of S is called a partition of S if each element of S belongs to exactly one of the members of P.

 
Proposition 2.2.5. Any partition P of a set S determines an equivalence relation.

 
Example 2.2.8 (Natural projection) Let S be any set, and let ~ be an equivalence relation on S. Define a function p : S -> S/~ by p(x) = [x], for all x in S. Proposition 2.2.3 shows that each element x in S belongs to a unique equivalence class, and so this shows that p is a function, which we refer to as the natural projection from S onto S/~.

For any x1, x2 in S we have x1 ~ x2 if and only if p(x1) = p(x2). This shows that p defines the original equivalence relation ~, so that the families S/~ and S/p are identical. This verifies the remark in Example 2.2.2 that every equivalence relation can be realized as the equivalence relation defined in a natural way by a function.

 
Theorem 2.2.6. If f : S -> T is any function, and ~ is the equivalence relation defined on S by letting

x1 ~ x2     if     f(x1) = f(x2),     for all x1, x2 in S,

then there is a one-to-one correspondence between the elements of the image f(S) of S under f and the equivalence classes S/f of the relation ~.

 
If f : S -> T is a function and y belongs to the image f(S), then the inverse image of y is

f -1(y) = { x in S | f(x) = y } .

The inverse images of elements of f(S) are the equivalence classes in S/f. (Note carefully that we are not implying that f has an inverse function.)



§ 2.2 Equivalence Relations: Solved problems

We first recall the informal definition of an equivalence relation.

Let S be a set. Then ~ defines an equivalence relation on S if and only if

(i) the reflexive law holds :
given any x in S, we always have x ~ x ;

(ii) the symmetric law holds :
given any x and y in S, if x ~ y , then y ~ x ;

(iii) the transitive law holds :
given any x, y and z in S, if x ~ y and y ~ z , then x ~ z .
When you check these conditions, remember that the symmetric law and transitive law start out by giving you pairs of similar elements. The reflexive law is different, because it just gives you an element of the set, with no extra conditions.

While working on these problems, you should remember that ordinary equality is the most basic equivalence relation. The most important example to keep in mind, though, is the equivalence relation on the set of integers that is defined by congruence modulo n. Equivalence relations are important because in a wide variety of situations it is useful to split a set up into subsets in which the elements have some property in common.

There are three different points of view in this section, looking at the one idea of splitting up a set S from three different vantage points:

The reason for considering several different points of view is that in a given situation one point of view may be more useful than another. Your goal should be to learn about each point of view, so that you can easily switch from one to the other. This is a big help in solving the problems, where you will sometimes need to decide which point of view will give the most useful approach.


14. On the set { (a,b) } of all ordered pairs of positive integers, define (x1,y1) ~ (x2,y2) if x1y2 = x2y1. Show that this defines an equivalence relation.     Solution

15. On the set C of complex numbers, define z1 ~ z2 if || z1 || = || z2 ||. Show that ~ is an equivalence relation.     Solution

16. Let u be a fixed vector in R3, and assume that u has length 1. For vectors v and w, define v ~ w if v · u = w · u, where · denotes the standard dot product. Show that ~ is an equivalence relation, and give a geometric description of the equivalence classes of ~ .     Solution

17. For the function f: R -> R defined by f(x) = x2, for all x in R, describe the equivalence relation on R that is determined by f.     Solution

18. For the linear transformation L: R3 -> R3 defined by

L(x,y,z) = (x + y + z, x + y + z, x + y + z) ,

for all (x,y,z) in R3, give a geometric description of the partition of R3 that is determined by L.     Solution

19. Define the formula f: Z12 -> Z12 by f ( [x]12 ) = [x]122, for all [x]12 in Z12. Show that the formula f defines a function. Find the image of f and the set Z12 / f of equivalence classes determined by f.     Solution

20. On the set of all n × n matrices over R, define A ~ B if there exists an invertible matrix P such that PAP-1 = B. Check that ~ defines an equivalence relation.     Solution


Solutions to the problems | Forward to §2.3 | Back to §2.1 | Up | Table of Contents