1. If R1 S T and R2 T U are binary relations, the composition of

R1 and R2 is the relation R1;R2 dened as:

R1;R2 := f(a; c) : There exists b 2 T such that (a; b) 2 R1 and (b; c) 2 R2g

(a) If f : S ! T and g : T ! U are functions is f; g a function?

(b) If R S S is transitive, show that R = R [ (R;R). (Hint: One

way to show A = B is to show A B and B A. One of these

directions is trivial.)

Let R S S be any binary relation on a set S. Consider the sequence

of relations R0;R1;R2; : : :, dened as follows:

R0 := R; and

Ri+1 := Ri [ (Ri;R) for i 0

(c) Prove that if Ri = Ri+1 for some i, then Ri = Rj for all j i.

(d) Prove that if Ri = Ri+1 for some i, then Rk Ri for all k 0.

(e) If jSj = n, explain why Rn = Rn+1. (Hint: Show that if (a; b) 2 Rn+1

then (a; b) 2 Ri for some i < n + 1.)

In the above sequence, Rn is dened to be the transitive closure of R,

denoted R (closely related to the operator used to describe the set of

all words over an alphabet).

(f) Show that R is transitive.