chapter  18
Equivalence Relations
Pages 6

Let S be a set. A relation on S is defined as follows. We choose a subset R ofthe Cartesian product S×S; in other words, R consists of some of the orderedpairs (s, t) with s, t ∈ S. For those ordered pairs (s, t) ∈ R, we write s ∼ t andsay s is related to t. And for (s, t) 6∈ R, we write s 6∼ t. Thus, the symbol ∼relates various pairs of elements of S. It is called a relation on S.This definition probably seems a bit strange at first sight. A few examplesshould serve to clarify matters. Example 18.1

Here are eight examples of relations on various sets S. (1) Let S =R, and define a∼ b⇔ a< b. Here R = {(s, t)∈R×R | s< t}. (2) Let S = Z and let m be a positive integer. Define a ∼ b ⇔ a ≡b mod m. (3) S = C, and a∼ b⇔ |a−b|< 1. (4) S = R, and a∼ b⇔ a + b ∈ Z. (5) S = {1,2}, and ∼ defined by 1∼ 1, 1∼ 2, 2 6∼ 1, 2∼ 2. (6) S = {1,2}, and ∼ defined by 1∼ 1, 1 6∼ 2, 2 6∼ 1, 2∼ 2. (7) S = all people in Britain, and a∼ b if and only if a and b have the

same father.