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
, 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)
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

[§]/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
e L;
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:
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."
Previous Page Next Page