Solution set of Homework Assignment 6

1.a) We can show that (Ro S)o T = Ro (So T) by showing that (Ro S)o T Í Ro (So T) and (Ro S)o T

Ê Ro (So T). We show first (Ro S)o T Í Ro ( So T). Suppose that (a, b) Î (Ro S)o T. Then there

exists an element x1 with x1 Î A such that (a, x1) Î T and (x1, b) Î Ro S. Furthermore since

(x1, b) Î R o S, there exists an element x2 with x2 Î A such that (x1, x2) Î S and (x2, b) Î R.

Now since (a, x1) Î T and (x1, x2) Î S, (a, x2) Î So T. Similarly since (a, x2) Î So T and

(x2, b) Î R, (a, b) Î Ro ( So T). Hence (Ro S)o T Í Ro (So T). Similarly we can show that

(Ro S)o T Ê Ro (So T). Thus (Ro S)o T = Ro (So T).

b) When n=1, it is trivially true that Ro R1 = R1o R. Assume that Ro Rn = Rn+1 i.e. Ro Rn = Rno R

for a positive integer n. This is the inductive hypothesis. Then

Ro Rn+1 = Ro (Rn o R ) ( by the definition of Rn+1 = Rno R )

= (Ro Rn)o R ( by the fact that (Ro S)o T = Ro (So T) )

= Rn+1o R ( by the inductive hypothesis )

= Rn+2 .

Thus Ro Rn = Rn+1 for all positive integers.

c) (Section 6.1, p.366 36.) We will use mathematical induction to prove that Rn is symmetric.

When n=1, by the assumption, Rn is symmetric. Assume that Rn is symmetric for a positive

integer n. We must show that this implies that Rn+1 is also symmetric. To show this, assume

that (a, b) Î Rn+1. Then since Rn+1 = Rn o R , there is an element x with xÎ A such that (a, x) Î R

and (x, b) Î Rn. Since R is symmetric, (x, a) Î R. The inductive hypothesis that Rn is

symmetric implies that (b, x) Î Rn. It follows that (b, a) Î Ro Rn . We know from b) that

Ro Rn = Rn+1. Therefore (b, a) Î Rn+1 . Hence Rn+1 is symmetric.

Thus Rn is symmetric for every positive integer n.

2.1) (Section 6.3, p.380, number 8)

2) Omitted.

3.(p.423, number 14)

a) R2: The relation R2 contains (a, b) if there is a mathematician c such that (a, c) Î R and

(c, b) Î R, that is, if there is a mathematician c such that a and b have written a paper together

and b and c have written a paper together.

b) R*: The relation R* contains (a, b) if there is a sequence of mathematicians, starting with a

and ending with b, such that each mathematician in the sequence has written a joint paper with

the next mathematician in the sequence.

c) We can define the Erd` s number of a mathematician m to be the length of a path from m to

Erd` s in R where there is a sequence of elements m, x1, x2, ¼ , xn-1, Erd` s with (m, x1) Î R,

(x1, x2) Î R, ¼ and (xn-1, Erd` s) Î R.

4.(Section 6.5, p.399, number 6)

Since R is an equivalence relation on a set A, an element of A belongs to its equivalence

class, [a]R. Then we can choose one representative of this equivalence class and make a

function which maps every element in the equivalence class to the representative. Clearly,

if f(x) = f(y) for any x and y, where (x, y)Î R. Conversely, for x and y such that f(x) = f(y),

there exists a representative c such that f(x) = f(y) = c and (x, y)Î [c]R.

5.(Section 6.5, p.401, number 28)

i)We first show that R1 Í R2 if P1 is a refinement of P2. Suppose that P1 is a refinement of P2.

We will show that if xR1y then xR2y. Assume that xR1y. Then there exists Ai such that

x, yÎ Ai, where { Ai | iÎ I } is P1. Since P1 is a refinement of P2, there exists Bj such that

Ai Í Bj, where { Bj | jÎ I } is P2. Therefore x, y Î Bj. It follows that xR2y. Thus R1 Í R2.

ii)Now we will show if R1 Í R2. P1 is a refinement of P2,. Suppose that R1 Í R2. We can show

that P1 is a refinement of P2 by showing that [a]R1 Í [a]R2 for any element a with a Î A.

Assume that c Î [a]R1. Then cR1a. Since R1 Í R2, it is true that cR2a. It follows that

c Î [a]R2. Thus [a]R1 Í [a]R2. This means that P1 is a refinement of P2.

From ii) and ii), R1 Í R2 if and only if P1 is a refinement of P2.

6.(Section 6.5, p.402, number 42)

A partition of { x1, x2, … , xn } can be obtained by first choosing some j, 0 £ j £ n-1, then

choosing j of the elements x1, x2, … , xn-1 to form a block of size j+1 with xn and then

partitioning the remaining (n-1)-j elements. Thus