342
Relations, Functions, and Matrices
partitions N into two equivalence classes. If x is an even number, then for any even
number y, x + y is even and y [ 3x 4. All even numbers form one class. If x is an
odd number and y is any odd number, x + y is even and y [ 3x 4. All odd numbers
form the second class. The partition can be pictured as in Figure 5.6. Notice again
that an equivalence class may have more than one name, or representative. In this
example, 32 4 = 38 4 = 310484, and so on; 31 4 = 317 4 = 39474, and so on.
evens
odds
N
Figure 5.6
Partitioning a set into equivalence classes is helpful because it is often convenient to go up one level of abstraction and treat the classes themselves as entities.
We will conclude this section with two important examples where this is the case
(you actually saw the first example somewhere around the fourth grade).
PRaCtiCe 14 For each of the following equivalence relations, describe the corresponding equivalence
classes.
a. On the set of all lines in the plane, x r y 4 x is parallel to y or x coincides with y.
b. On the set N, x r y 4 x = y.
c. On 51, 2, 36, r = 5(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)6.
■
example 14
Let S = 5a∙b 0 a, b [ Z, b ∙ 06. S is therefore the set of all fractions. The fractions
1∙2 and 2∙4 are different fractions—they have different numerators and different
denominators, but they are said to be “equivalent.” Formally, a∙b is equivalent
to c∙d, denoted by a∙b ∼ c∙d, if and only if ad = bc. We will show that the binary relation ∼ on S is indeed an equivalence relation. First, a∙b ∼ a∙b because
ab = ba. Also, if a∙b ∼ c∙d then ad = bc, or cb = da and c∙d ∼ a∙b. Hence,
∼ is reflexive and symmetric. To show that ∼ is transitive, let a∙b ∼ c∙d and
c∙d ∼ e∙f . Then ad = bc and cf = de. Multiplying the first equation by f and the
second by b, we get adf = bcf and bcf = bde. Therefore, adf = bde, or af = be
(why is it legitimate to divide by d here?). Thus, a∙b ∼ e∙f , and ∼ is transitive.
Some sample equivalence classes of S formed by this equivalence relation are
c
1
2
d = e c ,
−3
−6
,
−2
−4
,
−1
−2
,
1
2
,
2
4
,
3
6
, c f
c
3
10
d = e c ,
−9
−30
,
−6
−20
,
−3
−10
,
3
10
,
6
20
,
9
30
, c f
The set Q of rational numbers can be regarded as the set of all equivalence
classes of S. A single rational number, such as 31∙2 4, has many fractions representing it, although we customarily use the reduced fractional representation. When
we add two rational numbers, such as 31∙2 4 + 33∙104, we look for representatives
Relations, Functions, and Matrices
partitions N into two equivalence classes. If x is an even number, then for any even
number y, x + y is even and y [ 3x 4. All even numbers form one class. If x is an
odd number and y is any odd number, x + y is even and y [ 3x 4. All odd numbers
form the second class. The partition can be pictured as in Figure 5.6. Notice again
that an equivalence class may have more than one name, or representative. In this
example, 32 4 = 38 4 = 310484, and so on; 31 4 = 317 4 = 39474, and so on.
evens
odds
N
Figure 5.6
Partitioning a set into equivalence classes is helpful because it is often convenient to go up one level of abstraction and treat the classes themselves as entities.
We will conclude this section with two important examples where this is the case
(you actually saw the first example somewhere around the fourth grade).
PRaCtiCe 14 For each of the following equivalence relations, describe the corresponding equivalence
classes.
a. On the set of all lines in the plane, x r y 4 x is parallel to y or x coincides with y.
b. On the set N, x r y 4 x = y.
c. On 51, 2, 36, r = 5(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)6.
■
example 14
Let S = 5a∙b 0 a, b [ Z, b ∙ 06. S is therefore the set of all fractions. The fractions
1∙2 and 2∙4 are different fractions—they have different numerators and different
denominators, but they are said to be “equivalent.” Formally, a∙b is equivalent
to c∙d, denoted by a∙b ∼ c∙d, if and only if ad = bc. We will show that the binary relation ∼ on S is indeed an equivalence relation. First, a∙b ∼ a∙b because
ab = ba. Also, if a∙b ∼ c∙d then ad = bc, or cb = da and c∙d ∼ a∙b. Hence,
∼ is reflexive and symmetric. To show that ∼ is transitive, let a∙b ∼ c∙d and
c∙d ∼ e∙f . Then ad = bc and cf = de. Multiplying the first equation by f and the
second by b, we get adf = bcf and bcf = bde. Therefore, adf = bde, or af = be
(why is it legitimate to divide by d here?). Thus, a∙b ∼ e∙f , and ∼ is transitive.
Some sample equivalence classes of S formed by this equivalence relation are
c
1
2
d = e c ,
−3
−6
,
−2
−4
,
−1
−2
,
1
2
,
2
4
,
3
6
, c f
c
3
10
d = e c ,
−9
−30
,
−6
−20
,
−3
−10
,
3
10
,
6
20
,
9
30
, c f
The set Q of rational numbers can be regarded as the set of all equivalence
classes of S. A single rational number, such as 31∙2 4, has many fractions representing it, although we customarily use the reduced fractional representation. When
we add two rational numbers, such as 31∙2 4 + 33∙104, we look for representatives