Functions and Relations 123

even when they are identical enough in all the ways that matter for a particular purpose.

For example, if you are assembling a machine, you might consider all the type 6 hex-

head bolts as equivalent for the purpose of assembling the machine; although the bolts

are not identical as objects in the physical universe, they are nevertheless identical enough

for the purpose of assembling the machine. Because equivalence relations thus express a

concept of identity, mathematicians often use equality-like symbols, such as ≈, , ≡, and

∼, to represent the equivalence relations they are considering, and these symbols are often

defined and redefined with different meanings in different situations.

Mathematical examples abound. In the classical geometry of Euclid, similarity of trian-

gles is an equivalence relation. Congruency of geometric shapes is an equivalence relation.

The equality relation on rational numbers

1

2

=

3

6

amounts to an equivalence relation on

the fractional expressions representing those numbers, as the reader will verify in exer-

cise 11.1. In number theory, the relation of having the same parity (even/odd) is an equiv-

alence relation on the integers. In contemporary mathematics, an enormous number of

mathematical constructions proceed by defining a certain equivalence relation on a set and

then proceeding with that relation as a de facto identity relation.

Consider, for example, the relation of congruence-modulo-5 on the integers, commonly

written as a ≡

5

b, which holds when a and b have the same remainder when divided by 5,

in the sense of lemma 11.

Theorem 87. The relation of congruence-modulo-5 is reflexive, symmetric, and transitive.

Thus, it is an equivalence relation.

Proof. Every number has the same remainder as itself, when dividing by 5, and conse-

quently, congruence-modulo-5 is a reflexive relation a ≡

5

a. For symmetry, if a ≡

5

b, then

a and b have the same remainder when dividing by 5. It follows, of course, that b and a

have the same remainder, and so b ≡

5

a. So the relation is symmetric. For transitivity,

assume that a ≡

5

b and b ≡

5

c modulo 5. So a and b have the same remainder, and b

and c have the same remainder, when dividing by 5. So all three numbers have the same

remainder, and so in particular, a and c have the same remainder. So a ≡

5

c, verifying this

instance of transitivity.

It often happens in mathematics that one has an equivalence relation ∼ on a set A, and

one wants to define an operation on the equivalence classes, but one does so by making

reference to a particular element of the equivalence class, the representative of the class.

For example, perhaps one defines f ([a]) = g(a), meaning that the function f is meant to

take an equivalence class [a] as input, but the value of the function on [a] is defined by

applying g to a, which is only one element of [a]. This process can be subtly dangerous,

because one has succeeded in defining the operation on the equivalence classes, only when

g is well defined with respect to ∼, that is, when a ∼ b =⇒ g(a) = g(b). Let us illustrate

with an example.