130 Chapter 11
Use words precisely and accurately. Define your terms clearly, and respect those
definitions, taking them seriously. Know the meaning of the words you are using.
Recognize the definitions of others, which might be different from what you expect.
Think like a lawyer about the meaning of the assertions you read or make, as though
huge sums or your liberty were at stake. Recognize that words can have a precise
technical meaning. My advice to lawyers is, think like a mathematician!
Understand equivalence relations deeply. Use equivalence relations to get at the
essence of a concept. Take the quotient of a structure by an equivalence relation,
to bring that concept fully to the surface. Understand deeply what it means for an
operation or construction to be well defined with respect to an equivalence relation.
Exercises
11.1 Consider the collection of numerical expressions for rational numbers, like
3
4
or
−
6
12
. Let us
consider these expressions not as numbers but as syntactic expressions
p
q
, pairs of integers, a
numerator p and a nonzero denominator q, so that we count
1
2
as a different expression than
2
4
. Define the relation
p
q
≈
r
s
for such expressions if they represent the same rational number,
which happens precisely when ps = rq in the integers. Prove that this is an equivalence
relation.
11.2 Criticize this “proof.” Claim. Every transitive symmetric relation R on a set A is also reflexive.
Proof. Consider any a ∈ A, and suppose that aRb. By symmetry, we have also bRa.So
aRband bRa. By transitivity, therefore, aRa, and so the relation is reflexive.
11.3 Show that if ∼ and ≡ are two different equivalence relations on a set A, then the corresponding
sets of equivalence classes are not the same.
11.4 Show that congruence modulo n is a congruence with respect to addition and multiplication
on the integers, that is, that both addition and multiplication are well defined with respect to
congruence modulo n, for every positive integer n.
11.5 Is the squaring function x
2
well defined with respect to congruence modulo 5? How about
exponentiation 2
x
?
11.6 Criticize this calculation: The residue of the factorial 108! modulo 5 is 1, because 108! mod 5 =
(108 mod 5)! = 3! mod 5 = 6 mod 5 = 1.
11.7 Show that the correspondence of equivalence relations with partitions and the correspondence
of partitions with equivalence relations provided in the proofs of theorems 92 and 93, respec-
tively, are inverses of each other. That is, if ∼ is an equivalence relation on a set X and P is
the partition of X arising from ∼ in the proof of theorem 92, then the equivalence relation ∼
P
arising from P in the proof of theorem 93 is the same as the original relation ∼.