Please answer the questions below :

1. (5 points) Question 1: Reexive Closures Suppose we are given a relation R on a set S. Dene the relation R' as follows: R' = RU(s,s)|s E 8 That is to say, R' contains all the pairs in R, plus all pairs of the form (3, 3). Show that R' is the reexive closure of R. 2. (5 points) Question 2: Preservation Suppose that R is a binary relation on a set S, and P is a predicate on S that preserves R. Show that P also preserves P*, where P* is the reexive and transitive closure of R. 3. (6 points) Question 3: Transitive Closure The following is a more constructive denition of the transitive closure on a relation R. First, we dene the following sequence of sets of pairs. R0 = R (1) R141 2 Bi U {(s, u) | for some t, (s, t) E Riand(t,u) E Bi} (2) Another way to say this, is that we construct each R; + 1 by adding to R; all the pairs that can be obtained by \"one step of transitivity\" from pairs already in R. Finally, we dene the relation R+ as the union of all the Ri: R+ = U R1. (3) Show that R+ is the transitive closure of R