4. (40 pts.) Let R be a relation on the set of natural numbers de_ned by R = { (

ID: 3532957 • Letter: 4

Question

4. (40 pts.)

Let R be a relation on the set of natural numbers de_ned by

R = {(x, y) | y = x + 2}

(a) (5 pts.) List five ordered pairs from R.

(b) (5 pts.) List five ordered pairs from R^2.

(d) (25 pts.) Let C be the transitive closure of R. Prove (x, y) ? C implies x + y

is an even number. Do structural induction based on the recursive definition of

transitive closure.

Hint: For the basis, you need to prove (x, y) ?R implies x+y is even. Prove this

by cases, either x is odd or x is even.

Hint: For the induction, you need to prove (x, y) ? C and (y; z) ? C and x+y is

even and y + z is even implies x + z is even.

y=x+2

a)Pairs = (0,2),(1,3),(2,4),(3,5),(4,6)

b)Pairs from R^2 = (y=x^2 + 2) =(0,2),(1,3),(2,6),(3,11),(4,18)

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.