MATHOGRAPHICA L REMARKS 15

EXERCISE 10(G): (a) Let R be an equivalence relation on a set X. Prove that

X/R is a partition of X, i.e., that this family has the following two properties:

(i)lP7*) = *-

(2) For all A,B e X/R either A = B or AnB = ®.

(b) Show that if A' is a partition of a set X, then there exists exactly one equiv-

alence relation R on X such that X — X / R .

One can define relations and functions on a set X/R of equivalence classes in

terms of representatives. For example, on N/c

6

, we can define a relation L as

follows: {x/c6,y/c6) € L iff there are fc,!,m,nGN such that x = 6k+m, y — §l+n,

and m n 6. Or, one could define a function sq : N/CQ — N by: sq(x/c6) —

m2,

where x = 6k + m for some &, m G N with m 6.

Using this kind of definition, one should be on guard against a common fallacy.

To illustrate it, suppose we would like to define a function p on N/c

6

by

ip{x/c6)

—

[§]/c6 where [2] denotes the greatest integer not exceeding z. Then the function

value of ip for 4/c6 would be 2/c65 and the function value of p for 10/c6 would have

to be 5/c6- But this is a contradiction, since 4 and 10 are in the same equivalence

class of C^, whereas 2 and 5 are not.

Whenever we define a relation or function on a set of equivalence classes in

terms of representatives, we need to verify that the definition does not depend on

the particular choice of representatives.

EXERCISE 11(G): Verify that the function sq and the relation L given above

are well defined. That is, prove that if {x,x') G CQ and (y,y') G CQ, then

(a) (x/c„y/c6) e L iff

(x'/c6,yf/c6)

e L;

(b)

sq{x/c6)=sq{x'/c6)-3

Mathographical Remarks

Our notation is fairly standard, but in some cases, alternative notations are

used with about the same frequency. Many authors use (x,y) to denote the or-

dered pair (x,y). The image of a set A under a function / can be denoted by

f(A),f"A, f(A),f~*(A),fA) f~*A\ similarly for the inverse image, with arrows re-

versed. One often sees AB instead of BA. Equivalence classes of a relation R can

be rendered as [#], [x]R, ||x||, \\x\\R. Also, if R is a binary relation, it is usually more

convenient to write xRy instead of (x, y) G R. We shall follow the latter convention

in most of this book.

After reading this chapter, you should be able to determine whether you know

enough mathematics to benefit from this book. If reading the chapter and doing the

exercises felt comfortable, you are probably prepared to work through the material

ahead. "Feeling comfortable" doesn't mean that you did not have to think at all.

In fact, feeling comfortable with thinking about mathematical problems is perhaps

the most important prerequisite for reading this book.

But, if the preceding material gave you headaches, you may want to work

through a more elementary text on set theory before you return to this book.

A detailed coverage of the material in this section can be found in many books. We

recommend the following:

3

This somewhat informal notation is used instead of the more cumbersome phrase "The value

of sq does not depend on whether x or x' is used for its computation."