1.3. Equivalence Relations and Classes
Example 1.3.4(a):
Consider the set Z of all integers. Define a relation r by saying that
x and y are related if their difference y  x is
divisible by 2. Then
1. Equivalence Relation
 Check that this relation is an equivalence relation
 Find the two equivalence classes, and name them appropriately.
 How would you add these equivalence classes, if at all ?
 reflexive:
 x  x is equal to zero, which is divisible by two. Hence, every element is related to itself.
 symmetry:
 if x ~ y, then y  x is divisible by 2. But then  (y  x) = x  y is divisible by two. Hence, y ~ x
 transitivity:

 if x ~ y then y  x = 2n for some integer n
 if y ~ z then z  y = 2m for some integer m
Two elements are in the same equivalence class if and only if they are related. If x and y are in the same class, then y  x = 2n for some integer n.
 If y was even, then y = 2m for some integer m, and x = 2m  2n must also be even.
 If y was odd, then y = 2m + 1 for some integer m, and x = 2m + 1  2n must also be odd
 E = even numbers: E = [(2)] contains all even numbers
 O = odd numbers: O = [(3)] contains all odd numbers.
Define [x] + [y] = [x + y]. We need to show that this is welldefined, i.e. independent of the particular representative of the equivalence classes of [x] and [y]. Take x ~ x' and y ~ y'.
 Then x'  x = 2m and y'  y = 2n for some integers n and m.
 Then (x' + y')  (x + y) = x'  x + y'  y = 2m + 2n = 2 (m + n)
 [x] + [y] = [x + y] = [x' + y'] = [x'] + [y']
A better method would be the following: Define two classes 0 and 1 by saying:
 all numbers divisible by 2 with no remainder are in class 0
 all numbers divisible by 2 with remainder 1 are in class 1