__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 x_{1} with x_{1} Î A such
that (a, x_{1}) Î T and (x_{1}, b) Î Ro S. Furthermore since

(x_{1}, b) Î R o S,
there exists an element x_{2} with x_{2} Î A
such that (x_{1}, x_{2}) Î S and (x_{2},
b) Î R.

Now since (a, x_{1}) Î T and (x_{1}, x_{2})
Î S, (a, x_{2}) Î So T. Similarly since (a, x_{2}) Î
So T and

(x_{2}, 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 R^{1} =
R^{1o }R. Assume that Ro
R^{n }= R^{n+1} i.e. Ro R^{n} = R^{no }R

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

Ro R^{n+1 }= Ro (R^{n
o }R^{ }) ( by the definition of R^{n+1}
= R^{no }R )

= (Ro R^{n})o R ( by
the fact that (Ro S)o T = Ro (So T) )

= R^{n+1o }R ( by the inductive hypothesis )

= R^{n+2} .

Thus Ro R^{n }= R^{n+1} for all positive
integers.

c) (Section 6.1, p.366 36.) We will use mathematical induction to prove that R^{n }is
symmetric.

When n=1, by the assumption, R^{n }is symmetric. Assume that R^{n} is
symmetric for a positive

integer n. We must show that this implies that R^{n+1} is also symmetric. To
show this, assume

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

and (x, b) Î R^{n}. Since R is symmetric, (x, a) Î R. The inductive hypothesis that R^{n} is

symmetric implies that (b, x) Î R^{n}. It follows
that (b, a) Î Ro R^{n }.
We know from b) that

Ro R^{n }= R^{n+1}. Therefore (b, a) Î R^{n+1 }. Hence R^{n+1} is symmetric.

Thus R^{n} is symmetric for every positive integer n.

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

** **

2) Omitted.

3.(p.423, number 14)

a) R

^{2}: The relation R^{2}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 aand 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, x_{1}, x_{2}, ¼ , x_{n-1},
Erd` s with (m, x_{1}) Î R,

(x_{1}, x_{2}) Î R, ¼
and (x_{n-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 afunction 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 R

_{1}Í R_{2}if P_{1}is a refinement of P_{2}. Suppose that P_{1}is a refinement of P_{2}.We will show that if xR

_{1}y then xR_{2}y. Assume that xR_{1}y. Then there exists A_{i}such thatx, yÎ A

_{i}, where { A_{i }| iÎ I } is P_{1}. Since P_{1}is a refinement of P_{2}, there exists B_{j}such thatA

_{i Í }B_{j}, where { B_{j}| jÎ I } is P_{2}. Therefore x, y Î B_{j}. It follows that xR_{2}y. Thus R_{1}Í R_{2}.ii)Now we will show if R

_{1}Í R_{2}. P_{1}is a refinement of P_{2},. Suppose that R_{1}Í R_{2}. We can showthat P

_{1}is a refinement of P_{2 }by showing that [a]_{R1}Í [a]_{R2}for any element a with a Î A.Assume that c Î [a]

_{R1.}Then cR_{1}a. Since R_{1}Í R_{2}, it is true that cR_{2}a. It follows thatc Î [a]

_{R2}. Thus [a]_{R1}Í [a]_{R2}. This means that P_{1}is a refinement of P_{2}.From ii) and ii), R

_{1}Í R_{2}if and only if P_{1}is a refinement of P_{2}.6.(Section 6.5, p.402, number 42)

A partition of { x

_{1}, x_{2}, … , x_{n}} can be obtained by first choosing some j, 0 £ j £ n-1, thenchoosing j of the elements x

_{1}, x_{2}, … , x_{n-1}to form a block of size j+1 with x_{n}and thenpartitioning the remaining (n-1)-j elements. Thus