Forward to §2.3 | Back to §2.1 | Up | Table of Contents | About this document
Definition 2.2.1.
Let S be a set. A subset R of S × S is called an
equivalence relation
on S if
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
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 x_{1}, x_{2} in S we define
x_{1} ~ x_{2} if f(x_{1}) = f(x_{2}).
Then for all x_{1}, x_{2}, x_{3} in S we have
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_{1}, x_{2} in S we have x_{1} ~ x_{2} if and only if p(x_{1}) = p(x_{2}). 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_{1} ~ x_{2} if f(x_{1}) = f(x_{2}), for all x_{1}, x_{2} 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.)
Let S be a set. Then ~ defines an equivalence relation on S if and only if
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 (x_{1},y_{1}) ~ (x_{2},y_{2}) if x_{1}y_{2} = x_{2}y_{1}. Show that this defines an equivalence relation. Solution
15. On the set C of complex numbers, define z_{1} ~ z_{2} if || z_{1} || = || z_{2} ||. Show that ~ is an equivalence relation. Solution
16. Let u be a fixed vector in R^{3}, 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^{2}, for all x in R, describe the equivalence relation on R that is determined by f. Solution
18. For the linear transformation L: R^{3} -> R^{3} defined by
L(x,y,z) = (x + y + z, x + y + z, x + y + z) ,
for all (x,y,z) in R^{3}, give a geometric description of the partition of R^{3} that is determined by L. Solution19. Define the formula f: Z_{12} -> Z_{12} by f ( [x]_{12} ) = [x]_{12}^{2}, for all [x]_{12} in Z_{12}. Show that the formula f defines a function. Find the image of f and the set Z_{12} / 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