Formal MethodsKey to Homework Assignment 11, Part 3Wednesday, April 25, 20071. Suppose that ∼ is an equivalence relation on the nonempty set A. Also suppose thata and b are elements of A. Prove that [a] = [b] iff a ∼ b.Proof. We first prove that if [a] = [b], then a ∼ b. So suppose [a] = [b]. Recollect that[b] = {c ∈ A : b ∼ c}. Since ∼ is reflexive, b ∼ b. So b ∈ [b], and since [a] = [b], b ∈ [a].Since [a] = {c ∈ A : a ∼ c}, it must be the case that a ∼ b.Now we show that if a ∼ b, then [a] = [b]. So suppose a ∼ b. Then b ∈ a, since[a] = {c ∈ A : a ∼ c}. Furthermore, since ∼ is reflexive, b ∈ [b]. But then b ∈ [a] ∩ [b].Now {[a] : a ∈ A} is a partition of A. So either [a] ∩ [b] = ∅, or [a] = [b]. Sinceb ∈ [a] ∩ [b], [a] ∩ [b] 6= ∅, and hence [a] = [b].2. For each of the pairs (a, b), determine whether a ≡ b (mod n).(a) (a, b) = (18, 36), n = 10.18 − 36 = −18, which is not divisible by 10. So 18 6≡ 36 (mod 10).(b) (a, b) = (18, 36), n = 12.18 − 36 = −18, which is not divisible by 12. So 18 6≡ 36 (mod 12).(c) (a, b) = (1378, 294), n = 172.1378 − 294 = 1084, which is not evenly divisible by 172 (1084 = 6 · 172 + 52). So1378 6≡ 294 (mod 172).3. For each of the following integers a, find an integer b such that 0 ≤ b < n anda ≡ b (mod n).(a) a = 2763, n = 10.2763 = 276 · 10 + 3. So 2763 ≡ 3 (mod 10).(b) a = 2763, n = 172.2763 = 172 · 16 + 11. So 2763 ≡ 11 (mod 172).(c) a = 2763, n = 693.2763 = 693 · 3 + 684. So 2763 ≡ 684 (mod 693).159. For each real number b, let Ab= {(x, y) ∈ R×R : y = |x+b|}, and let A = {Ab: b ∈ R}.Is A a partition of R × R? Justify your answer.No, A is not a partition of R × R. For suppose b = 1 and c = −1. Then Ab6= Ac,because, for example, (2, 3) ∈ Ab, but (2, 3) 6∈ Ac. However, (0, 1) ∈ Ab∩ Ac. ThusAb6= Acand Ab∩ Ac6= ∅.60. For each real number b, let Ab= {(x, y) ∈ R×R : y = |x|+b}, and let A = {Ab: b ∈ R}.Is A a partition of R × R? Justify your answer.Yes, A is a partition of R ×R. To see this, observe first that Ab6= ∅, because (0, b) ∈ Ab.Also, if (x, y) ∈ R × R, then by choosing b = y − |x|, we see that (x, y) ∈ Ab. That is,∪A = R × R.So it remains to be shown that either Ab∩ Ac= ∅ or Ab= Ac. So suppose that(x0, y0) ∈ Ab∩ Ac. Then b = y0− |x0| = c. So b = c, and Ab= Ac.63. Prove that if a ≡ b (mod n) and c ≡ d (mod n), then a − c ≡ b − d (mod n).Proof. Since a ≡ b (mod n) and c ≡ d (mod n), there exist integers r and s, suchthata − b = rn and c − d = sn.So(a − b) − (c − d) = rn − sn.This equation is equivalent to the equation(a − c) − (b − d) = (r − s)n.Since r − s is an integer, we have that a − c ≡ b − d (mod