Advanced High-School Mathematics

200 CHAPTER 4 Abstract Algebra

4.1.5 Relations and equivalence relations

LetSbe a set. ArelationRonSis simply a subset ofS×S. Nothing
more, nothing less. If (x,y)∈R⊆S×S, then we typically writexRy
and say thatxis related toy. A few examples might clarify this.

(i) LetRbe the relation “<” on the setRof real numbers. Therefore,

R = {(x,y)∈R×R|x < y}.

(ii) Fix a positive integermand recall that ifa∈Zthenm|a means

thatais a multiple ofm. Now letRbe the relation on the setZ

of integers defined by

aRb⇔m|(a−b).

Note that we already met this relation in Section 2.1.3.

This relation is, as we have seen, customarily denoted “mod m”

and read “congruence modulom.” Thus ifm= 7, then we can say

that 1≡15 (mod 7)” where we read this as “1 is congruent to 15

modulo 7.”

Note, in particular, that if m = 7 then the integers which are

congruent modulo 7 to −1 are precisely those of the form −1 +

7 k, k= 0,± 1 ,± 2 , ....

(iii) LetS={ 1 , 2 , 3 , 4 , 5 , 6 }. We may express a relationRonSby

specifying a matrix P containing 0s and 1s and where the rows

and columns are labeled by the elements of S in the order 1, 2,

3, 4, 5, and 6 and where a “1” in rowiand columnjdesignates

thatiRj. More specifically, let’s consider the relation defined as

by the matrix: