Bridge to Abstract Mathematics: Mathematical Proof and Structures

238 RELATIONS: EQUIVALENCE RELATIONS AND PARTIAL ORDERINGS Chapter 7

Solution Let A= (1,2,3) and define R,, on A by R,, = ((1, 1),(2,2),

(3, 3), (1,2), (2, l), (1, 3), (3, 1)). R,, is clearly reflexive on A (due to the

presence of the first three ordered pairs) and symmetric. But R,, is not

transitive; for example, (2, 1) and (1, 3) are in R,,, but (2, 3) is not.

For our second example, let A = R and recall from Exercise 5(c),

Article 7.1, the relation R,, = ((x, y) E R x Rl lx - yl 5 1). For any

x E R, lx - xl = 0 I 1, so R,, is reflexive. If x, y E R with ix - ~1 I 1,

then ly - xl = Ix - yl I 1, so that R,, is symmetric. R,, is not transitive

since, for example, (4, i) E R,, and (i, y) E R,,, but (2, y) 4 R,,.

Discovering relations similar to those in Example 4, involving the other

combinations of R, S, and T is the goal of Exercise 8.

The most important fact to understand about equivalence relations is

that each equivalence relation on a set A generates a unique partition of

A, and vice versa. This correspondence is the topic of the next article. In

the following definition, based on Exercise 11, Article 7.1, we take a first

step toward this correspondence.

DEFINITION 2

Given a relation R on a set A, define for eaoh x E A the set [x] by the rule [x] =

{YE A~(x, y) E Rf. The set [x] is the subset of A consisting of all elements of A to

which x is related. If R is an equivalence relation on A, we call [x] the equiva-

lence class determined by x and denote by the symbol AIR the set ([x] I x E A)

of all equivalence classes.

EXAMPLE 5 (a) The relations R,, = ((1, l), (2,2), (3, 3), (4,4), (1,2), (2, 3),

(3, 2), 3), (3, (4, 5), (5, 4)) and R3 2 = ((2, 21, (39 3), (47 4), (5, 5)7 (3, 419

(4, 3), (3, 5), (5, 3), (4, 5), (5,4)) are not equivalence relations on A =

(1, 2, 3,4, 5). Calculate PI, [2], [3], [4], and [5] for both relations.

(b) The relation R,, = ((1, I), (27 2), (3,3), (4,4), (5, 5), (2951, (5, a,

(3, 5), (5, 3), (2, 3), (3,2)) & an equivalence relation on A = (1,2, 3,4, 5).

Calculate AIR,,.

/'

,/' Solution

(a) For R,,, [I] = (1, 2, 31, [2] = (2, 31, [3] = (1, 2, 31, [4] =

(4,5), and [5] = (4). For R3,, we have [I] = (a, [2] = (21, 133 =

{3,4,5), [4] = {3,4,!}, and [5] = (3,4, 55.

(b) For the equivalence relation R,,, p] = (1), [4] = (41, and

[2] = D] = [5] = {2,3,5). Thus AIR,, = ((I), {4), {2,3,5}).^0

Note the qualitative difference between the results in (a) and those in

(b) of Example 5. The subsets generated in (b) present a much "tidier" pic-

ture than those in (a). Specifically, the sets [m] in (b) have the properties

that all are nonempty, any two of them are either identical or disjoint, and

each element of A is contained in at least one of them. The collections

k generated by R, , and R3, both fail to have at least one of these three prop-