代做CS 131 – Problem Set 5代做迭代

CS 131 - Problem Set 5

Problems must be submitted by Monday October 24, 2021 at 11:59pm, on Gradescope.

All the proofs below should be paragraph proofs and need to be  in clear prose. Mathematical  notation  within  the  prose  is  both  allowed  and  encouraged  if it  makes  the  proof clearer. For the examples of proofs, see notes for lectures 13 and later, posted on Piazza.

Problem 1. (30 points, 10 each) Consider the following relations on the set R2 .  For each of them, state whether it is transitive and prove your answer in paragraph.  If you think the relation is not transitive, you still need to write paragraph proof to explain your counterexample.  (R is a set of real numbers. R2 = R × R is the set of all points (x, y) where x and y are real numbers )

a)  R1  = {((x, y), (z, t)): (jx - z j > 1) ∧ (jy - tj > 1)}

b)  R2  = {((x, y), (z, t)): (x > z) ∧ (y > t)}

c)  R3  = {((x, y), (z, t)): (x > z) ∨ (y > t)}

Problem 2.   (10 points) Prove that if a and b are integers and 5 j a, then 5 j ab.

Problem  3.      (15  points)  Define  multiples(x)  as  {y  ∈  Z: x j y}.    Prove  that  multiples(69)   multiples(23).

Problem 4.   (15 points) Let a and b be two integers.  Prove that

divisors(a) ∩ divisors(b) = divisors(b) ∩ divisors(a - b),

via the following two steps.  We will grade only the first part; the second part is very similar and thus we do not require you to submit it and will not grade it.

a)  (15 points) Prove that divisors(b) ∩ divisors(a - b)  divisors(a) ∩ divisors(b)

b)   (0  points  — neither required nor graded) Prove that  divisors(a) ∩ divisors(b)   divisors(b) ∩ divisors(a - b).

Problem 5.   (15 points) Prove that if 131 does not divide 111x, then 131 does not divide x.

Problem 6.   (15 points) Prove that if a ∈ Z and b  Z then c = a + b  Z