Let R be the relation defined in Example.a. Prove that R

Chapter 8, Problem 42E

(choose chapter or problem)

Problem 42E

Let R be the relation defined in Example.

a. Prove that R is reflexive.

b. Prove that R is symmetric.

c. List four distinct elements in [(1, 3)].

d. List four distinct elements in [(2, 5)].

Example

Rational Numbers Are Really Equivalence Classes

For a moment, forget what you know about fractional arithmetic and look at the numbers

as symbols. Considered as symbolic expressions, these appear quite different. In fact, if they were written as ordered pairs

(1, 3) and (2, 6)

they would be different. The fact that we regard them as “the same” is a specific instance of our general agreement to regard any two numbers

as equal provided the cross products are equal: ad = bc. This can be formalized as follows, using the language of equivalence relations.

Let A be the set of all ordered pairs of integers for which the second element of the

pair is nonzero. Symbolically,

A = Z × (Z –{0}).

Define a relation R on A as follows: For all (a, b), (c, d) ∈ A,

(a, b) R (c, d) ⇔ ad = bc.

The fact is that R is an equivalence relation.

a. Prove that R is transitive. (Proofs that R is reflexive and symmetric are left to the

exercises.)

b. Describe the distinct equivalence classes of R.

Solution

a. [We must show that for all (a, b), (c, d), (e, f ) ∈ A, if (a, b) R (c, d) and (c, d)R (e, f ), then (a, b) R (e, f ).] Suppose (a, b), (c, d), and (e, f ) are particular but arbitrarily chosen elements of A such that (a, b) R (c, d) and (c, d) R (e, f ). [We must show that (a, b) R (e, f ).] By definition of R,

(1) ad = bc and (2) cf = de.

Since the second elements of all ordered pairs in A are nonzero, b ≠ 0, d ≠0, and f ≠ 0. Multiply both sides of equation (1) by f and both sides of equation (2) by b to obtain

(1′) ad f = bcf and (2′) bcf = bde.

Thus

ad f = bde

and, since d ≠ 0, it follows from the cancellation law for multiplication (T7 in Appendix A) that

a f = be.

It follows, by definition of R, that (a, b) R (e, f ) [as was to be shown].

b. There is one equivalence class for each distinct rational number. Each equivalence class consists of all ordered pairs (a, b) that, if written as fractions a/b, would equal each other. The reason for this is that the condition for two rational numbers to be equal is the same as the condition for two ordered pairs to be related. For instance, the class of (1, 2) is

[(1, 2)] = {(1, 2), (–1,–2), (2, 4), (–2,–4), (3, 6), (–3,–6),…}

Since and so forth.