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