Bridge to Abstract Mathematics: Mathematical Proof and Structures

244 RELATIONS: EQUIVALENCE RELATIONS AND PARTIAL ORDERINGS Chapter 7

-7, -2, 3, 8, 13, 18,.. .I, {... , -11, -6, -1,4,9, 14, 19,.. .)I, a collec-

tion of subsets of Z, which we may now recognize as a five-celled partition

of Z, where each cell is infinite. This may be abbreviated to Z/=, = ([O],

[I], [a], [3], [4]), where you will note that [2], for instance, consists pre-

cisely of those integers that yield a remainder of 2 when divided by 5, in

accordance with the division algorithm theorem (recall Exercise 4, Article

7.2). In Chapter 9 where we study certain algebraic structures, we will see

that many sets of equivalence classes such as Z/=, may be equipped with

algebraic operations resembling, or based on, ordinary addition and mul-

tiplication of real numbers. The resulting mathematical structures, often

called quotient structures, are the basis for many important mathematical

constructions. Included among these is the theory of quotient groups and

rings (topics from the area of abstract algebra), the development of the

rational number system from the integers, and the development of the real

number system from the rationals. We will get a taste of the latter two

topics in Chapter 10.

Exercises

1. Describe the partition of the set A = {a, b, c, d, e, f) corresponding to the equiv-
   alence relations:


2. Describe, by listing all ordered pairs, the equivalence relation on the set A =
   {a, b, c, d, e, f) corresponding to the partitions:


3. Referring to the equivalence relations defined in Articles 7.1, 7.2, and 7.3 of the
   text, describe the partition of the appropriate set A determined by each of the
   following equivalence relations. When possible, determine explicitly the number of
   cells in each partition:
   (a) R, = {(x, y) I x and y are both male or both female), A = set of all people living
   in 1987
   *(b) R, = {(m, n)^1 m and n are both even or both odd), A = Z
   (c) R,,={(m,n)(m=n),A=Z
   (d) R,, = {(M, N)ln(~) = n(N)), A = ax), where X = {1,2,... ,9, 10)
   fe) R19 = {(x, y)lx2 = y2), A = R
   (f) The relation "congruence modulo 9" on Z, from Exercise 5(a), Article 7.2