Is R reflexive? Symmetric? Transitive? If a property does not hold, say why.
3. Consider the relation R = ©(a, b),(a, c),(c, b),(b, c)ª on the set A = ©a, b, cª. Is R
reflexive? Symmetric? Transitive? If a property does not hold, say why.
Properties of Relations
183
4. Let A = ©a, b, c, dª. Suppose R is the relation
R
=
©(a, a),(b, b),(c, c),(d, d),(a, b),(b, a),(a, c),(c, a),
(a, d), (d, a), (b, c), (c, b), (b, d), (d, b), (c, d), (d, c)ª.
Is R reflexive? Symmetric? Transitive? If a property does not hold, say why.
p
p
p p
5. Consider the relation R = ©(0,0),( 2,0),(0, 2),( 2, 2)ª on R. Is R reflexive?
Symmetric? Transitive? If a property does not hold, say why.
6. Consider the relation R = ©(x, x) : x ∈ Zª on Z. Is R reflexive? Symmetric?
Transitive? If a property does not hold, say why. What familiar relation is
this?
7. There are 16 possible different relations R on the set A = ©a, bª. Describe all of
them. (A picture for each one will suffice, but don’t forget to label the nodes.)
Which ones are reflexive? Symmetric? Transitive?
8. Define a relation on Z as xR y if |x−y| < 1. Is R reflexive? Symmetric? Transitive?
If a property does not hold, say why. What familiar relation is this?
9. Define a relation on Z by declaring xR y if and only if x and y have the same
parity. Is R reflexive? Symmetric? Transitive? If a property does not hold, say
why. What familiar relation is this?
10. Suppose A 6= ;. Since ; ⊆ A × A, the set R = ; is a relation on A. Is R reflexive?
Symmetric? Transitive? If a property does not hold, say why.
11. Suppose A = ©a, b, c, dª and R = ©(a, a),(b, b),(c, c),(d, d)ª. Is R reflexive? Symmet-
ric? Transitive? If a property does not hold, say why.
12. Prove that the relation | (divides) on the set Z is reflexive and transitive. (Use
Example 11.8 as a guide if you are unsure of how to proceed.)
13. Consider the relation R = ©(x, y) ∈ R × R : x − y ∈ Zª on R. Prove that this relation
is reflexive, symmetric and transitive.
14. Suppose R is a symmetric and transitive relation on a set A, and there is an
element a ∈ A for which aR x for every x ∈ A. Prove that R is reflexive.
15. Prove or disprove: If a relation is symmetric and transitive, then it is also
reflexive.
16. Define a relation R on Z by declaring that xR y if and only if x2 ≡ y2 (mod 4).
Prove that R is reflexive, symmetric and transitive.
17. Modifying the above Exercise 8 (above) slightly, define a relation ∼ on Z as x ∼ y
if and only if |x − y| ≤ 1. Say whether ∼ is reflexive. Is it symmetric? Transitive?
18. The table on page 179 shows that relations on Z may obey various combinations
of the reflexive, symmetric and transitive properties. In all, there are 23 =
8 possible combinations, and the table shows 5 of them. (There is some
redundancy, as ≤ and | have the same type.) Complete the table by finding
examples of relations on Z for the three missing combinations.
184
Relations
11.2 Equivalence Relations
The relation = on the set Z (or on any set A) is reflexive, symmetric
and transitive. There are many other relations that are also reflexive,
symmetric and transitive. Relations that have all three of these properties
occur very frequently in mathematics and often play quite significant roles.
(For instance, this is certainly true of the relation = .) Such relations are
given a special name. They are called equivalence relations.
Definition 11.3
A relation R on a set A is an equivalence relation if
it is reflexive, symmetric and transitive.
As an example, Figure 11.2 shows four different equivalence relations
R1, R2, R3 and R4 on the set A = ©−1,1,2,3,4ª. Each one has its own meaning,
as labeled. For example, in the second row the relation R2 literally means
“has the same parity as.” So 1R2 3 means “1 has the same parity as 3,” etc.
Relation R
Diagram
Equivalence classes
(see next page)
“is equal to” (=)
−1
1
2
© − 1ª ©
©
, 1ª,
2ª,
R1 = ©(−1,−1),(1,1),(2,2),(3,3),(4,4)ª
©3ª ©4ª
3
4
,
“has same parity as”
−1
1
2
© − 1,1,3ª ©
,
2, 4ª
R2 = ©(−1,−1),(1,1),(2,2),(3,3),(4,4),
(−1,1),(1,−1),(−1,3),(3,−1),
3
4
(1, 3), (3, 1), (2, 4), (4, 2)ª
“has same sign as”
−1
1
2
R
©
©
3 = ©(−1, −1), (1, 1), (2, 2), (3, 3), (4, 4),
− 1ª,
1, 2, 3, 4ª
(1, 2), (2, 1), (1, 3), (3, 1), (1, 4), (4, 1), (3, 4),
3
4
(4, 3), (2, 3), (3, 2), (2, 4), (4, 2), (1, 3), (3, 1)ª
“has same parity and sign as”
−1
1
2
© − 1ª ©
©
,
1, 3ª,
2, 4ª
R4 = ©(−1,−1),(1,1),(2,2),(3,3),(4,4),
(1, 3), (3, 1), (2, 4), (4, 2)ª
3
4
Figure 11.2. Examples of equivalence relations on the set A = ©−1,1,2,3,4ª
Equivalence Relations
185
The above diagrams make it easy to check that each relation is reflexive,
symmetric and transitive, i.e., that each is an equivalence relation. For
example, R1 is symmetric because xR1 y ⇒ yR1 x is always true: When x = y
it becomes T ⇒ T (true), and when x 6= y it becomes F ⇒ F (also true). In
a similar fashion, R1 is transitive because (xR1 y ∧ yR1 z) ⇒ xR1 z is always
true: It always works out to one of T ⇒ T, F ⇒ T or F ⇒ F. (Check this.)
As you can see from the examples in Figure 11.2, equivalence relations
on a set tend to express some measure of “sameness” among the elements
of the set, whether it is true equality or something weaker (like having
the same parity).
It’s time to introduce an important definition. Whenever you have
an equivalence relation R on a set A, it divides A into subsets called
equivalence classes. Here is the definition:
Definition 11.4
Suppose R is an equivalence relation on a set A. Given
any element a ∈ A, the equivalence class containing a is the subset
©x ∈ A : xRaª of A consisting of all the elements of A that relate to a. This
set is denoted as [a]. Thus the equivalence class containing a is the set
[a] = ©x ∈ A : xRaª.
Example 11.9
Consider the relation R1 in Figure 11.2. The equivalence
class containing 2 is the set [2] = ©x ∈ A : xR12ª. Because in this relation
the only element that relates to 2 is 2 itself, we have [2] = ©2ª. Other
equivalence classes for R1 are [−1] = © − 1ª, [1] = ©1ª, [3]
= ©3ª and [4] = ©4ª.
Thus this relation has five separate equivalence classes.
Example 11.10
Consider the relation R2 in Figure 11.2. The equivalence
class containing 2 is the set [2] = ©x ∈ A : xR22ª. Because only 2 and 4 relate
to 2, we have [2] = ©2, 4ª. Observe that we also have [4] = ©x ∈ A : xR24ª =
©2,4ª, so [2] = [4]. Another equivalence class for R2 is [1] = ©x ∈ A : xR21ª
= © − 1, 1, 3ª. In addition, note that [1] = [−1] = [3] = © − 1,1,3ª. Thus this
©
©
relation has just two equivalence classes, namely 2, 4ª and
− 1, 1, 3ª.
Example 11.11
The relation R4 in Figure 11.2 has three equivalence
classes. They are [−1] = © − 1ª and [1] = [3] = ©1, 3ª and [2] = [4] = ©2, 4ª.
Don’t be misled by Figure 11.2. It’s important to realize that not
every equivalence relation can be drawn as a diagram involving nodes
and arrows. Even the simple relation R = ©(x, x) : x ∈ Rª, which expresses
equality in the set R, is too big to be drawn. Its picture would involve a
point for every real number and a loop at each point. Clearly that’s too
many points and loops to draw.
186
Relations
We close this section with several other examples of equivalence rela-
tions on infinite sets.
Example 11.12
Let P be the set of all polynomials with real coefficients.
Define a relation R on P as follows. Given f (x), g(x) ∈ P, let f (x) R g(x) mean
that f (x) and g(x) have the same degree. Thus (x2 + 3x − 4) R (3x2 − 2) and
(x3 + 3x2 − 4) 6R (3x2 − 2), for example. It takes just a quick mental check to
see that R is an equivalence relation. (Do it.) It’s easy to describe the
equivalence classes of R. For example, [3x2 + 2] is the set of all polynomials
that have the same degree as 3x2 + 2, that is, the set of all polynomials of
degree 2. We can write this as [3x2 + 2] = ©ax2 + bx + c : a, b, c ∈ R, a 6= 0ª.
Example 11.8 proved that for a given n ∈ N the relation ≡ (mod n) is
reflexive, symmetric and transitive. Thus, in our new parlance, ≡ (mod n)
is an equivalence relation on Z. Consider the case n = 3. Let’s find the
equivalence classes of the equivalence relation ≡ (mod 3). The equivalence
class containing 0 seems like a reasonable place to start. Observe that
[0] = ©x ∈ Z : x ≡ 0(mod 3)ª =
©x ∈ Z : 3 | (x − 0)ª = ©x ∈ Z : 3 | xª = ©...,−3,0,3,6,9,...ª.
Thus the class [0] consists of all the multiples of 3. (Or, said differently,
[0] consists of all integers that have a remainder of 0 when divided by 3).
Note that [0] = [3] = [6] = [9], etc. The number 1 does not show up in the
set [0] so let’s next look at the equivalence class [1]:
[1] = ©x ∈ Z : x ≡ 1(mod 3)ª = ©x ∈ Z : 3 | (x − 1)ª = ©...,−5,−2,1,4,7,10,...ª.
The equivalence class [1] consists of all integers that give a remainder of
1 when divided by 3. The number 2 is in neither of the sets [0] or [1], so
we next look at the equivalence class [2]:
[2] = ©x ∈ Z : x ≡ 2(mod 3)ª = ©x ∈ Z : 3 | (x − 2)ª = ©...,−4,−1,2,5,8,11,...ª.
The equivalence class [2] consists of all integers that give a remainder of
2 when divided by 3. Observe that any integer is in one of the sets [0], [1]
or [2], so we have listed all of the equivalence classes. Thus ≡ (mod 3) has
exactly three equivalence classes, as described above.
Similarly, you can show that the equivalence relation ≡ (mod n) has n
equivalence classes [0], [1], [2], . . . , [n − 1].
Equivalence Relations
187
Exercises for Section 11.2
1. Let A = ©1,2,3,4,5,6ª, and consider the following equivalence relation on A:
R = ©(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(2,3),(3,2),(4,5),(5,4),(4,6),(6,4),(5,6),(6,5)ª
List the equivalence classes of R.
2. Let A = ©a, b, c, d, eª. Suppose R is an equivalence relation on A. Suppose R has
two equivalence classes. Also aRd, bR c and eRd. Write out R as a set.
3. Let A = ©a, b, c, d, eª. Suppose R is an equivalence relation on A. Suppose R has
three equivalence classes. Also aRd and bR c. Write out R as a set.
4. Let A = ©a, b, c, d, eª. Suppose R is an equivalence relation on A. Suppose also
that aRd and bR c, eRa and cR e. How many equivalence classes does R have?
5. There are two different equivalence relations on the set A = ©a, bª. Describe
them. Diagrams will suffice.
6. There are five different equivalence relations on the set A = ©a, b, cª. Describe
them all. Diagrams will suffice.
7. Define a relation R on Z as xR y if and only if 3x − 5y is even. Prove R is an
equivalence relation. Describe its equivalence classes.
8. Define a relation R on Z as xR y if and only if x2 + y2 is even. Prove R is an
equivalence relation. Describe its equivalence classes.
9. Define a relation R on Z as xR y if and only if 4|(x+3y). Prove R is an equivalence
relation. Describe its equivalence classes.
10. Suppose R and S are two equivalence relations on a set A. Prove that R ∩ S
is also an equivalence relation. (For an example of this, look at Figure 11.2.
Observe that for the equivalence relations R2, R3 and R4, we have R2 ∩ R3 = R4.)
11. Prove or disprove: If R is an equivalence relation on an infinite set A, then R
has infinitely many equivalence classes.
12. Prove or disprove: If R and S are two equivalence relations on a set A, then
R ∪ S is also an equivalence relation on A.
13. Suppose R is an equivalence relation on a finite set A, and every equivalence
class has the same cardinality m. Express |R| in terms of m and |A|.
14. Suppose R is a reflexive and symmetric relation on a finite set A. Define
a relation S on A by declaring xS y if and only if for some n ∈ N there are
elements x1, x2, . . . , xn ∈ A satisfying xR x1, x1R x2, x2R x3, x3R x4, . . . , xn−1R xn, and
xnR y. Show that S is an equivalence relation and R ⊆ S. Prove that S is the
unique smallest equivalence relation on A containing R.
15. Suppose R is an equivalence relation on a set A, with four equivalence classes.
How many different equivalence relations S on A are there for which R ⊆ S?
188
Relations
11.3 Equivalence Classes and Partitions
This section collects several properties of equivalence classes.
Our first result proves that [a] = [b] if and only if aRb. This is useful
because it assures us that whenever we are in a situation where [a] = [b],
we also have aRb, and vice versa. Being able to switch back and forth
between these two pieces of information can be helpful in a variety of
situations, and you may find yourself using this result a lot. Be sure to
notice that the proof uses all three properties (reflexive, symmetric and
transitive) of equivalence relations. Notice also that we have to use some
Chapter 8 techniques in dealing with the sets [a] and [b].
Theorem 11.1
Suppose R is an equivalence relation on a set A. Suppose
also that a, b ∈ A. Then [a] = [b] if and only if aRb.
Proof. Suppose [a] = [b]. Note that aRa by the reflexive property of R,
so
a ∈ ©x ∈ A : xRaª = [a] = [b] = ©x ∈ A : xRbª
©
. But a belonging to x ∈ A : xRbª
means aRb. This completes the first part of the if-and-only-if proof.
Conversely, suppose aRb. We need to show [a] = [b]. We will do this by
showing [a] ⊆ [b] and [b] ⊆ [a].
First we show [a] ⊆ [b]. Suppose c ∈ [a]. As c ∈ [a] = ©x ∈ A : xRaª, we get
cRa. Now we have cRa and aRb, so cRb because R is transitive. But cRb
implies c ∈ ©x ∈ A : xRbª = [b]. This demonstrates that c ∈ [a] implies c ∈ [b],
so [a] ⊆ [b].
Next we show [b] ⊆ [a]. Suppose c ∈ [b]. As c ∈ [b] = ©x ∈ A : xRbª, we get
cRb. Remember that we are assuming aRb, so bRa because R is symmetric.
Now we have cRb and bRa, so cRa because R is transitive. But cRa implies
c ∈ ©x ∈ A : xRaª = [a]. This demonstrates that c ∈ [b] implies c ∈ [a]; hence
[b] ⊆ [a].
The previous two paragraphs imply that [a] = [b].
■
To illustrate Theorem 11.1, recall how we worked out the equivalence
classes of ≡ (mod 3) at the end of Section 11.2. We observed that
[−3] = [9] = ©...,−3,0,3,6,9,...ª.
Note that [−3] = [9] and −3 ≡ 9 (mod 3), just as Theorem 11.1 predicts. The
theorem assures us that this will work for any equivalence relation. In the
future you may find yourself using the result of Theorem 11.1 often. Over
time it may become natural and familiar; you will use it automatically,
without even thinking of it as a theorem.
Equivalence Classes and Partitions
189
Our next topic addresses the fact that an equivalence relation on a set
A divides A into various equivalence classes. There is a special word for
this kind of situation. We address it now, as you are likely to encounter it
in subsequent mathematics classes.
Definition 11.5
A partition of a set A is a set of non-empty subsets of
A, such that the union of all the subsets equals A, and the intersection of
any two different subsets is ;.
Example 11.13
©©
Let A = ©a, b, c, dª. One partition of A is
a, bª, ©cª, ©dªª.
©
©
©
This is a set of three subsets a, bª,
cª and dª of A. The union of the
three subsets equals A; the intersection of any two subsets is ;.
Other partitions of A are
©©a, bª,©c, dªª,
©©a, cª,©bª,©dªª,
Book of Proof Page 26