Bridge to Abstract Mathematics: Mathematical Proof and Structures

234 RELATIONS: EQUIVALENCE RELATIONS AND PARTIAL ORDERINGS Chapter 7

Partial proof We consider the "only if" part of (e). Suppose R n R- ' = I,.

To prove A = B, let x E A be given. Then (x, x) E I,. Since I, = R n R - ',

then (x, x) E R. Since R is a relation from A to B, we must have x E B.

Thus A G B. The fact that B G A can be proved in an identical manner.

To show that R is antisymmetric, suppose that (x, y) E R and (y, x) E R,

we claim x = y. Since (y, x) E R, then (x, y) E R- ', SO that (x, y) E

R n R- ' = I,. Hence, by definition of I,, we conclude x = y, as desired.

Proving the remaining properties is left to you in Exercises 9

and 10.

Exercises

1. (a) Prove that the cross product distributes over intersection [Theorem l(b)].
   (6) Prove that (X - Y) x Z G (X x 2) - (Y x Z) for any three sets X, Y, and 2.
   (c) Prove parts (d), (e), and (f) of Theorem 1.


2. Write down five specific ordered pairs in each of the following relations from
   Example 2 through 6 of the text:


3. (a) Write symbolically, using quantifiers and ordered pair notation, the defi-
   nitions of R is transitive and R is antisymmetric. [Hint: See (a) and (b) of Defi-
   nition 3.1
   (b) Write symbolically, using quantifiers and ordered pair notation, the negation
   of each of the four parts of Definition 3. (e.g., What is the precise meaning of
   "R is not reflexive"?)


4. Determine which of the four properties; reflexive, symmetric, antisymmetric, and
   transitive, are possessed by each of the relations R, through R17 in Examples 1
   through 6.


5. Determine which of the four properties from Exercise 4 are satisfied by each of
   the following relations on the set R of all real numbers:
   J
   (a) R18={(x,~)l~=1/x) (b) R19={(x,~)lx2=~2}
   (c) R2,= {(x,y)lIx-ylI 13 (d) R,, = {(x,y)lxf Y)


6. (a) Show that if A is a nonempty set, then the relation R = (21 on A is symmetric
   and transitive, but not reflexive.
   (b) Give an example of a relation R #^0 on a set A which is symmetric and
   transitive, but not reflexive.
   (c) Find a flaw in the following argument, which purports to prove "a relation
   R # (21 on a set A, which is symmetric and transitive, is necessarily reflexive."
   "Proof" Let x E A. We claim (x, x) E R. Choose y E A such that (x, y) E R. Since
   R is symmetric and (x, y) E R, then (y, x) E R. Since R is transitive, and since
   both (x, y) and (y, x) are in R, we conclude (x, x) E R, as desired.