Formal MethodsKey to Homework Assignment 10, Part 3Wednesday, April 18, 20071. Suppose P is the family of propositional expressions. Recollect that if P and Q arepropositional expressions, then P ⇔ Q iff P and Q always have the same truth value.Prove that ifL = {(P, Q) ∈ P × P : P ⇔ Q},then L is an equivalence relation. (You can use any facts from Chapter 1.)Proof. If P is a propositional expression, then P always has the same truth value asitself. So L is reflexive. Also if P and Q are propositional expressions and P alwayshas the same truth value as Q, then Q always has the same truth value as P. So L isalso reflexive.To see that L is transitive suppose that P, Q, and R are propositional expressions suchthat P always has the same truth value as Q and Q always has the same truth valueas R. Then if P is true, Q is true, and hence R is true. A similar argument shows thatif P is false, then R must also be false. So P always has the same truth value as Rand L is transitive.2. We can define another relation on P as follows:I = {(P, Q) ∈ P × P : P → Q is a tautology }.Then I is almost an equivalence relation. However, it fails to have one of the threerequired properties. Which one? Give an example that illustrates the property thatfails.I isn’t symmetric. For example, suppose P is the propositional expression x ∈ {1} andQ is the propositional expression x ∈ {1, 2}, then P → Q is a tautology. So (P, Q) ∈ I.However, Q → P is not a tautology. If x = 2, Q is true, but P is false.26. Let R = {(a, b) ∈ R × R : ∃ an integer k such that a − b = 2kπ}.(a) Prove that R is an equivalence relation.Proof. R is reflexive because if a is any real number, then a − a = 0 = 2 · 0 · π.R is also symmetric because if (a, b) ∈ R, then a − b = 2kπ for some integer k.Hence b − a = 2(−k)π, and since k is an integer, so is −k.1To see that R is transitive, suppose that (a, b) and (b, c) belong to R. Then thereexist integers k1and k2such that a − b = 2k1π and b − c = 2k2π. Soa − c = (a − b) + (b − c) = 2k1π + 2k2π = 2(k1+ k2)π.Since k1and k2are integers, k1+ k2is also an integer, and we see that (a, c) ∈ R.(b) List three members of [π/4].We want real numbers b such that π/4−b = 2kπ, for some integer k. Equivalently,then, we wantb = π/4 − 2kπ,So we might choose k = −1, 0, 1, and this would give us b = −7π/4, π/4, 9π/4,respectively.(c) List three members of [1].This is similar to the preceding part, except that now we want to choose b so thatb = 1 − 2kπ,for some integer k. Choosing k = −1, 0, 1 again, we get b = 1 − 2π, 1, 1 + 2π,respectively.(d) Which numbers, if any, belong to [π/4] ∩ [1].The intersection is empty. To see this, suppose to the contrary, that there areintegers m and n such thatπ/4 − 2mπ = 1 − 2nπ.This is equivalent toπ(1/4 − 2m + 2n) = 1.Since m and n are integers, −2m + 2n is an integer and 1/4 − 2m + 2n is nonzero.But 1/4 − 2m + 2n is rational. So when we divide both s ides by it, we getπ =11/4 − 2m + 2n,or π is rational, which is a contradiction.28. Let R = {(x, y) ∈ R × R : x2− y2= 0}.(a) Prove that R is an equivalence relation.Proof. R is reflexive since x2−x2= 0. It’s also symmetric, because if x2−y2= 0,then y2− x2= −(x2− y2) = 0.To see that R is transitive, suppose that (x, y) and (y, z) belong to R. Thenx2− y2= 0 and y2− z2= 0. Sox2− z2= x2− y2+ y2− x2= 0 + 0 = 0,and (x, z) ∈ R.2(b) List all the members of [3].y ∈ [3] iff 32− y2= 0, or, equivalently, iff y2= 9. So [3] = {3, −3}.29. Let R = {(3, 5)}. Is R symmetric? Is R transitive?R isn’t symmetric: (3, 5) ∈ R, but (5, 3) ∈ R. However, R is transitive. To see thisobserve that in order for R to be transitive, it must be the case that whenever (x, y) and(y, z), belong to R, (x, z) also belongs to R. However, the hypothesis (x, y) and (y, z)belong to R, could be true only if (x, y) = (3, 5) and (y, z) = (5, z) or (x, y) = (x, 3)and (y, z) = (3, 5). Since (3, 5) is the only element of R, R has no element of the form(5, z) and it has no element of the form (x, 3). So the hypothesis “(x, y) and (y, z)belong to R” must be false, and an implication with a false hypothesis is always true.So R is transitive.31. Let R = {(a, b) ∈ N × N : a divides b}. Is R reflexive on N? symmetric? transitive?Prove your answers.(a) R is reflexive. For if a is any natural number 1 · a = a. So a divides a and(a, a) ∈ R.(b) R is not symmetric. To see this we need to find a pair (a, b) such that (a, b) ∈ R,but (b, a) /∈ R . For example, if we choose a = 2 and b = 4. Then a divides b, butb doesn’t divide a. So (2, 4) ∈ R, but (4, 2) /∈ R.(c) R is transitive. To see this, suppose that a, b, and c are natural numbers suchthat (a, b) and (b, c) belong to R. Then a divides b and b divides c. So there existintegers m and n such that am = b and bn = c. Substituting am for b in thesecond equation gives (am)n = a(mn) = c. Since mn is an integer, a divides c.34. Let R be the set of natural numbers and consider the following subsets of R × R.(a) R1= {(x, y) ∈ R × R : xy = 0}.(b) R3= {(x, y) ∈ R × R : xy 6= 0}.(d) R4= {(x, y) ∈ R × R : x ≥ y}.Which of the above relations is(i) Reflexive on R?(ii) Symmetric?(iii) Transitive?(a) R1is not reflexive. For example, (1, 1) /∈ R1, since 1 · 1 6= 0.R1is symmetric. If xy = 0, then by commutativity yx = 0. So if (x, y) ∈ R1, then(y, x) ∈ R1.R1is not transitive. For example, suppose that x = 1, y = 0, and z = 1. Thenxy = yz = 0. So (x, y) ∈ R1and (y, z) ∈ R1. However, xz = 1. So (x, z) /∈ R1.3(b) R3is not reflexive. (0, 0) /∈ R3.R3is symmetric, once again by the commutative law for multiplication: If (x, y) ∈R3, then xy 6= 0. So yx 6= 0, and (y, …