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.

 
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 }.

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

x₁ ~ x₂     if     f(x₁) = f(x₂).

 
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 x₁, x₂ in S we have x₁ ~ x₂ if and only if p(x₁) = p(x₂). 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

x₁ ~ x₂     if     f(x₁) = f(x₂),     for all x₁, x₂ in S,

 
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 } .

§ 2.2 Equivalence Relations: Solved problems

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 .

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:

• First there is the definition of an equivalence relation on S, which tells you when two different elements of S have the same properties and therefore belong to the same subset.

• Then there is the notion of a partition of S, which places the emphasis on describing the subsets.

• Finally, Example 2.2.2 and Example 2.2.8 show that every equivalence relation (or partition) really comes from some function f : S -> T, where we say that x₁ and x₂ are equivalent if f(x₁) = f(x₂).

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 (x₁,y₁) ~ (x₂,y₂) if x₁y₂ = x₂y₁. Show that this defines an equivalence relation.     Solution

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

16. Let u be a fixed vector in R³, 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) = x², for all x in R, describe the equivalence relation on R that is determined by f.     Solution

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

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

19. Define the formula f: Z₁₂ -> Z₁₂ by f ( [x]₁₂ ) = [x]₁₂², for all [x]₁₂ in Z₁₂. Show that the formula f defines a function. Find the image of f and the set Z₁₂ / 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