190
CHAPTER 3 Relations
13. Prove Theorem 4.
14. There is an old, fallacious proof that if a relation is both symmetric and transitive, it is
reflexive. We give this "proof" below. What is the error?
Suppose R is a symmetric and transitive relation on a set X. Pick an x E X.
We need to show x R x. So, take any y where x R y. By symmetry, it follows
that y R x. By transitivity, it follows that x R x.
15. For a relation R on a set X, let R* denote the reflexive and transitive closure of R.
(a) For any relation R on a set X, define a relation -' on X as follows: x - y if and
only if x R* y and y R* x. Prove that - is an equivalence relation.
(b) Let xl - x2 and yj - Y2. Show that x1 R* yi if and only if x2 R* Y2.
16. (a) For k, n1, n2, ml, m2 E N, show that if
nn 2 (modk)
and
ml
m 2 (modk)
then
nt + ml
n2 + m 2 (modk)
and
nli
ml -n2 • m2(mod k)
(b) Part (a) says that if we take two equivalence classes [ m ] and [ n ], then we can
unambiguously define [m ] + [ n ] and []
[ n ]. Pick any mI I [ m ] and any
n I E [ n ], and define
[mi]+[n] = [ml +ni]
and
[m] • [n]--[ml - ni]
The definition is unambiguous since it doesn't matter which ml and nl we
pick. Find the addition and multiplication tables for the equivalence classes of
- (mod 4) and =- (mod 5). (Hint: For both =- (mod 4) and - (mod 5), your answer should include
[0]+[0] -[0], [01+[1] -[1], [01 . [0]- [0]
and
but, for -- (mod 4),
whereas, that will be false for
(mod 5).)