122 Chapter 11

and notation. Namely, first, the divides relation a | b is not at all the same thing as the

fractional expression b/a. The expression b/a, after all, represents a number, the numerical

result of dividing the number b by the number a, and similarly with a/b; but an instance of

the divides relation a | b, in contrast, is not a number at all—it is a statement, a statement

describing how a and b are related. The divides relation a | b is true exactly when a

divides an integral number of times into b. Second, please take care with the order of the

numbers in these expressions, because when we write a | b for distinct positive integers,

for example, then a is the factor and b is the multiple; this is the divides relation, rather

than the divisible-by relation.

Theorem 85. The divides relation a | b on the set of natural numbers is reflexive and

transitive but not symmetric.

Proof. (Reflexive) The divides relation is reflexive since every number divides itself: a | a,

since a · 1 = a.

(Transitive) To see that the divides relation is transitive, suppose that a | b and that b | c.

Since a | b, there is a number k such that ak = b. Since b | c, there is a number r such that

br = c

. Putting these two facts together, we see that a(kr ) = (ak )r = br = c, and so we see

that a | c, as desired.

(Not symmetric) The divides relation is not symmetric, since 3 | 6 but it is not the case

that 6 | 3.

Similarly, the reader can easily verify that the usual less-than relation < on the integers

is nonreflexive, nonsymmetric, but transitive. The less-than-or-equal-to relation ≤, in con-

trast, is reflexive and transitive but not symmetric.

11.2 Equivalence relations

It is difficult to overstate the importance and ubiquity of the equivalence relation concept

in mathematics. This notion arises in nearly every area of pure mathematics and should be

seen as a general conceptual tool.

Definition 86. An equivalence relation is a relation that is reflexive, symmetric, and tran-

sitive.

Equivalence relations generalize the principle features of one of the most important rela-

tions there is, the relation of identity a = b, which is, of course, reflexive, symmetric, and

transitive. In short,

equality is an equivalence relation.

Thus, equivalence relations are a kind of identity relation; we use them when we want to

consider softer concepts of identity, involving only the relevant aspects of individuals while

ignoring irrelevant differences that would cause two objects to be strictly nonidentical,