Important Announcement
PubHTML5 Scheduled Server Maintenance on (GMT) Sunday, June 26th, 2:00 am - 8:00 am.
PubHTML5 site will be inoperative during the times indicated!

Home Explore Mathematical Logic and Proving Techniques Lecture Notes

Mathematical Logic and Proving Techniques Lecture Notes

Published by Fairuz Shohaimay, 2019-08-15 23:54:09

Description: Lecture Notes with Past Semester Questions
Intended for use by CS111 UiTM Kampus Raub only

Search

Read the Text Version

Exercise 3.15 March 2016 Q6 Use the Forward-Backward Method to prove the following proposition. If ������ and ������ are two even integers then 4 divides 3������y + 3������y. Your answer should have an analysis of the proof and the condensed proof. 145

Exercise 3.16 June 2019 Q8 Prove the following proposition using the forward-backward method. If ������ and ������ are two consecutive positive integers, then ������y + ������y + 2 is an odd number. Show the analysis of the proof and the condensed proof. 146

3.4 The Construction Method The quantifier ‘there is’ appears in many mathematical statements. Consider the following definitions. Definition 3.11 A real number r is rational if and only if there are integers ������ and ������ with ������ ≠ 0 such that ������ = NO. Definition 3.12 An integer ������ is square if there is an integer ������ such that ������ = ������y. Most of the existential quantified statement has the basic structure: There is an ‘object’ with a ‘certain property’ such that ‘something happens’. Example 3.7 1. There is an integer ������ > 2 such that ������y − 5x + 6 = 0. Object: integer ������. Certain property: ������ > 2 Something happens: ������y − 5x + 6 = 0 2. There are real numbers ������ and ������ both > 0 such that 2x + 3y = 8 and 5x − y = 3. Object: real numbers ������ and ������ Certain property: ������, ������ > 0 Something happens: 2x + 3y = 8 and 5x − y = 3 3. ∃ an angle ������ ∋ cos(������) = ������. Object: angle ������ Certain property: none Something happens: cos(������) = ������ 147

When proving that ‘������ implies ������’ is true, suppose we obtain a statement in forward process that has the quantifier ‘there is’ in the standard form. ������: There is an ‘object’ with a ‘certain property’ such that ‘something happens’. Steps: 1. Assume there is an object (i.e. ������) 2. This object with its certain property and the something that happens should help to reach the conclusion that ������ is true. But if the quantifier ‘there is’ is encountered during the backward process, then it must be shown that ������: There is an ‘object’ with ‘certain property’ such that ‘something happens’. Here, we use the Construction Method. Construction Method (Existential Quantifier ‘there is’ in the Backward Process) I. Identify a) Object b) Certain property c) Something happens II. Obtain a new statement in the forward process a) Use the hypothesis (and creativity) to construct the desired object. b) A new statement is the one with the constructed object. III. Obtain a new statement in the backward process a) Show that the constructed object (from Step II) has the certain property and satisfy the something that happens. 148

SUMMARY Dealing with Statements that has Existential Quantifier Suppose we obtain a statement that has the quantifier ‘there is’ in the … Forward Process Backward Process ������: There is an ‘object’ with a ‘certain ������: There is an ‘object’ with a ‘certain property’ such that ‘something happens’. property’ such that ‘something happens’. USE ➡ Forward-Backward Method USE ➡ Construction Method 1. Assume there is an ‘object’. 1. Identify • ‘object’, ‘certain property’ and 2. This ‘object’ with its ‘certain property’ ‘something happens’. and ‘something happens’ should help to prove that ������ is true. 2. Obtain a new statement in the forward process. • Use the hypothesis (and creativity) to construct the ‘object’. 3. Obtain a new statement in the backward process. • Show that the ‘constructed object’ has the ‘certain property’ and satisfy ‘something happens’. 149

Example 3.8 If ������, ������, ������, ������, ������, and ������ are real numbers such that ������������ − ������������ ≠ 0, then the two equations ������������ + ������������ = ������ and ������������ + ������������ = ������ can be solved for the real numbers ������ and ������. Analysis of Proof: ������: ������, ������, ������, ������, ������, and ������ are real numbers such that ������������ − ������������ ≠ 0 ������: The two equations ������������ + ������������ = ������ and ������������ + ������������ = ������ can be solved for the real numbers ������ and ������. ������1: There are real numbers ������ and ������ such that ������������ + ������������ = ������ and ������������ + ������������ = ������ Construction Method ������1: Construct real numbers ������ = êëIâè and ������ = ááêèIIâìëì. (Note that ������������ − ������������ ≠ 0) áêIâì ������2: Prove that ������������ + ������������ = ������ and ������������ + ������������ = ������ ������2: (������������ − ������������)������ = ������������ − ������������______(1) and (������������ − ������������)������ = ������������ − ������������______(2) ������3: ������ × (1) = (3): (������������ − ������������)������������ = ������������������ − ������������������ and ������ × (1) = (5): (������������ − ������������)������������ = ������������������ − ������������������ ������ × (2) = (4): (������������ − ������������)������������ = ������������������ − ������������������ ������ × (2) = (6): (������������ − ������������)������������ = ������������������ − ������������������ ������4: (3) + (4): (������������ − ������������)(������������ + ������������) = ������������������ − ������������������ (������������ − ������������)(������������ + ������������) = (������������ − ������������)������ ������������ + ������������ = ������ and (5) + (6): (������������ − ������������)(������������ + ������������) = ������������������ − ������������������ (������������ − ������������)(������������ + ������������) = (������������ − ������������)������ ������������ + ������������ = ������ ������4 ⟺ ������2 Proof Complete Condensed Proof: 150

Example 3.9 Prove that if ������ and ������ are rational numbers and ������ ≠ 0, then î is a rational number. é Analysis Proof: ������: ������ and ������ are rational numbers and ������ ≠ 0 ������: î is a rational number. é ������1: There are integers ������ and ������ with ������ ≠ 0 such that î = NO. é Construction Method ������1: Construct integers ������ and ������. ������2: Show that ������ = ������ ������ ������ ������2: Let ������ = ������/������ and ������ = ������/������ where ������, ������, ������, and ������ are integers with ������, ������ ≠ 0. ������ = ������������ïï������������ ������ ������3: ������ ������ = ������ × ������ ������4: ������ = ������ where ������ = ������������, ������ = ������������ ≠ 0. ������ ������ ������4 ⟺ ������2 Proof Complete Condensed Proof: Because ������ and ������ are rational, then there are integers ������, ������, ������, and ������ are integers with ������, ������ ≠ 0 such that ������ = ������/������ and ������ = ������/������. Since ������ ≠ 0, then ������ ≠ 0. Constructing ������ = ������������, and ������ = ������������ ≠ 0, it follows that î = é ¤áâ¥ï¤êì ¥ = áê = NO, and hence î is rational, thus completing the proof. âì é 151

Example 3.10 Prove that if ������ < ������ are consecutive integers and ������ is even, then 4 divides ������y + ������y − 1. Analysis of Proof: ������1: ������ < ������ are consecutive integers and ������ is even ������: 4 divides ������y + ������y − 1. ������1: There is an integer ������ such that ������y + ������y − 1 = 4������. Construction Method ������1: Construct integer ������. ������2: Prove that ������y + ������y − 1 = 4������. ������2: ������ is even and ������ is odd. ������3: Let ������ = 2������ and ������ = 2������ + 1 where ������ is an integer. ������4: ������y + ������y − 1 = (2������)y + (2������ + 1)y − 1 = 4������y + 4������y + 4������ + 1 − 1 = 8������y + 4������ = 4(2������y + ������) ������5: ������y + ������y − 1 = 4������ where ������ = 2������y + ������ ������5 ⟺ ������2 Proof Complete Condensed Proof: 152

Exercise 3.17 March 2012 Q10(a) Briefly explain when the construction method of proof is used in proving the conditional statement ������ → ������. Exercise 3.18 March 2014 Q7(b) Use the construction method to prove that: If ������ and ������ are rational and ������ ≠ 0, then ð is rational. j Your answer should have an analysis of the proof only. 153

Exercise 3.19 September 2014 Q10 Use the construction method, prove the following. If the function ������(������) = 3������ + 2 is continuous in the interval [2, 6], then there exist a value ������ that satisfy the Mean Value Theorem. Your answer should have an analysis of proof and the condensed proof. [HINT: The Mean Value Theorem states that if ������(������) is continuous on [������, ������], then there is a number ������ between ������ and ������ such that ∫áâ ������(������)������������ = ������(������) ∙ (������ − ������)] 154

3.5 The Choose Method Consider the following standard form for a statement with universal quantifier. For every ‘object’ with ‘certain property’, ‘something happens’. Example 3.11 1. For every angle ������, siny ������ + cosy ������ = 1. Object: angle ������ Certain property: none Something happens: siny ������ + cosy ������ = 1 2. ∀ real numbers ������ > 0, ∃ a real number ������ ∋ 2Ø = ������. Object: real number ������ Certain property: ������ > 0 Something happens: ∃ a real number ������ ∋ 2Ø = ������. If we encounter the quantifier ‘for all’ in the backward process, then it must be shown that ������: For every ‘object’ with a ‘certain property’, ‘something happens’. We use the Choose method. Choose Method (Universal Quantifier ‘For all’ in the Backward Process) I. Identify a) Object b) Certain property c) Something happens II. Obtain a new statement in the forward process a) Choose an ‘object’ with ‘certain property’. III. Obtain a new statement in the backward process a) Show that for the chosen ‘object’ (from Step II), the ‘something happens’. 155

Example 3.12 Suppose in we want to show that ������: For all real numbers ������ with ������y − 3������ + 2 ≤ 0, 1 ≤ x ≤ 2. Choose Method I. Identify a) Object: real numbers ������ b) Certain property: ������y − 3������ + 2 ≤ 0 c) Something happens: 1 ≤ ������ ≤ 2 II. Forward process (Obtain new statement) a) Choose an object with the certain property. ������1: Let an element ������ be a real number with ������y − 3������ + 2 ≤ 0. III. Backward process (Obtain new statement) a) Show that for the chosen object, something happens. ������1: 1 ≤ ������ ≤ 2 Consider the following definitions. Definition 3.13 A set ������ is a subset of a set ������ (written ������ ⊆ ������) if and only if for each element ������ ∈ ������, ������ ∈ ������. Definition 3.14 Two sets ������ and ������ are equal (written ������ = ������) if and only if ������ is a subset of ������ and ������ is a subset of ������. These definitions will be helpful in the following example. Example 3.13 If ������ and ������ are the two sets defined by ������ = {real numbers ������: ������y − 3������ + 2 ≤ 0} ������ = {real numbers ������: 1 ≤ ������ ≤ 2}, then ������ ⊆ ������. 156

Analysis of Proof: ������: ������ and ������ are the two sets defined by ������ = {real numbers ������: ������y − 3������ + 2 ≤ 0} and ������ = {real numbers ������: 1 ≤ ������ ≤ 2} ������: ������ ⊆ ������ ������1: For each element ������ ∈ ������, ������ ∈ ������ Choose Method ������1: Choose an element ������ ∈ ������. ������2: Prove that ������ ∈ ������ ������3: 1 ≤ ������ ≤ 2 ������2: ������y − 3������ + 2 ≤ 0 ������3: (������ − 2)(������ − 1) ≤ 0 ������4: Either ������ − 1 ≤ 0 ∪ ������ − 2 ≥ 0, or ������ − 1 ≥ 0 ∩ ������ − 2 ≤ 0. ������5: It must be that ������ ≥ 1 ∪ ������ ≤ 2, so that quadratic inequality has nonpositive solution. ������6: 1 ≤ ������ ≤ 2 ������6 ⟺ ������3 Proof Complete Condensed Proof: From the hypothesis, S and T are two sets defined by ������ = {real numbers ������: ������y − 3������ + 2 ≤ 0} and ������ = {real numbers ������: 1 ≤ ������ ≤ 2}. Let an element ������ ∈ ������, then ������ ∈ ������. Either ������ − 1 ≤ 0 ∪ ������ − 2 ≥ 0, or ������ − 1 ≥ 0 ∩ ������ − 2 ≤ 0. It must be that ������ ≥ 1 ∪ ������ ≤ 2, so that quadratic inequality has nonpositive solution. Thus, ������ ⊆ ������. 157

Exercise 3.20 March 2012 Q7 ������ and ������ are two sets defined by: ������ = {real numbers ������: ������y − 4 ≤ 0} ������ = {real numbers ������: −2 ≤ ������ ≤ 2} By using the choose method, prove that ������ ⊆ ������. Your answer should have an analysis of proof and the condensed proof. 158

Exercise 3.21 March 2013 Q7 Write an analysis of the proof and condensed proof for the proposition given below using the choose method. If ������ and ������ are real numbers with ������ > 0, and ������ is the function defined by ������(������) = ������������ + ������, then for all real numbers ������ and ������ with ������ < ������, ������(������) < ������(������). 159

Exercise 3.22 March 2014 Q8 ������ and ������ are two sets defined as follows: ������ = {real number ������: ������y − 4������ + 3 ≥ 0} ������ = {real number ������: ������ ≤ 1 or ������ ≥ 3} Prove using the choose method that ������ ⊆ ������. Your answer should have an analysis of the proof and the condensed proof. 160

Exercise 3.23 March 2015 Q10 Prove the following proposition using Choose Method. For every real number ������ > 2 , there is a real number ������ < 0 such that ������ = ¬yGÙÙ. Write the analysis of proof and condensed proof. 161

Exercise 3.24 March 2016 Q9 Prove the proposition using the Choose Method. If ������(������) = (������ − 1)y and ������(������) = ������ + 1, then ������ ≥ ������ on the set ������ = {real numbers ������: 0 ≤ ������ ≤ 3}. Your answer should have an analysis of the proof and the condensed proof. [Hint : Suppose that ������ and ������ are functions of one variable. Then ������ ≥ ������ on the set ������ of real numbers if and only if for every element ������ ∈ ������, ������(������) ≥ ������(������).] 162

Exercise 3.25 October 2016 Q9 Prove the following proposition using the Choose Method. If ������(������) = (2������ − 1)y and ℎ(������) = ������ + 1, then ������ ≥ ℎ on the set ������ = Lreal numbers ������: ������ ≤ 0 or x ≥ Ê-S Your answer should have an analysis of the proof and the condensed proof. [Hint : Suppose that ������ and ℎ are functions of one variable. Then ������ ≥ ℎ on the set ������ of real numbers if and only if for every element ������ ∈ ������, ������(������) ≥ ℎ(������).] 163

Exercise 3.26 March 2017 Q7 If S and Tare two sets defined by ������ = {������ ∈ ������: ������y + 8������ + 7 ≤ 0} ������ = {������ ∈ ������: −7 ≤ ������ ≤ −1} Prove that ������ ⊆ ������ by using Choose Method. Show the analysis of proof and condensed proof. 164

Exercise 3.27 December 2018 Q8 Prove using choose method. If ������ and ������ are two sets defined by ������ = {real number ������: ������y + 2������ − 15 ≤ 0} ������ = {real number ������: −5 ≤ ������ ≤ 3} then ������ ⊆ ������. Show the analysis of proof only. 165

Exercise 3.28 June 2019 Q9 Consider the following condensed proof of the proposition, If ������ is a positive integer, then for all nonzero integers ������ and ������ having the same sign and for which ������ > ������ , O > Nó. N Proof. Because ������ and ������ have the same sign, N > 0. Now ������ > ������ , so multiplying both (Oó) side of ������ > ������ by N results in óN > NOOó . It now follows that N > Nó, so the proof is complete. (Oó) Oó O a) Write the analysis of proof for the above condensed proof. b) Hence, state the method used in the proof and the reason for using the method. 166

3.6 The Specialization Method If we are working forward with a quantified statement ‘for all’, then it is assumed that ������: For every ‘object’ with ‘certain property’, ‘something happens’. We use the Specialization method. Specialization Method (Universal Quantifier ‘For all’ in the Forward Process) I. Identify a) Object b) Certain property c) Something happens II. Look for one particular ‘object’ to apply specialization to. a) Usually obtain from the Choose method (backward process). III. Verify that this particular ‘object’ does have the ‘certain property’ specified in the ‘for all’ statement. IV. Obtain a new statement in the forward process that ‘something happens’ for this particular ‘object’. Definition 3.15 A real number ������ is an upper bound for a set of real numbers ������ if and only if for every element ������ ∈ ������, ������ ≤ ������. Definition 3.16 Suppose that ������ and ������ are functions of one variable. Then ������ ≥ ������ on the set ������ of real numbers if and only if for every element ������ ∈ ������, ������(������) ≥ ������(������). Example 3.14 Prove that for sets ������, ������, and ������, if ������ ⊆ ������ and ������ ⊆ ������, then ������ ⊆ ������. Analysis of Proof: ������: ������ ⊆ ������ and ������ ⊆ ������ ������: ������ ⊆ ������ ������1: For every element ������ ∈ ������, ������ ∈ ������. (By definition of ������ ⊆ ������) Choose Method ������1: Choose an element ������ ∈ ������. ������2: Show that ������ ∈ ������ ������2: For every element ������ ∈ ������, ������ ∈ ������. (From hypothesis and definition of ������ ⊆ ������) 167

Specialization Method ������3: ������ ∈ ������ (From ������1 & ������2) ������4: For every element ������ ∈ ������, ������ ∈ ������. (From hypothesis and definition of ������ ⊆ ������) Specialization Method ������5: ������ ∈ ������ (From ������3 & ������4) ������5 ⟺ ������2 Proof Complete Condensed Proof: To show that ������ ⊆ ������, we must show that for every ������ ∈ ������, ������ ∈ ������. From the hypothesis ������ ⊆ ������, then let an element ������ ∈ ������, so ������ ∈ ������. Also, ������ ⊆ ������ and it follows that ������ ∈ ������. Hence, proof is complete. SUMMARY Dealing with Statements that has Universal Quantifier Suppose we obtain a statement that has the quantifier ‘for all’ in the … Forward Process Backward Process ������: For all ‘objects’ with ‘certain property’, ������: For all ‘objects’ with ‘certain property’, ‘something happens’. ‘something happens’. USE ➡ Specialization Method USE ➡ Choose Method 1. Identify 1. Identify • ‘object’, ‘certain property’, and • ‘object’, ‘certain property’, and ‘something happens’ ‘something happens’ 2. Look for a particular ‘object’ to apply 2. Obtain a new statement in the forward specialization to. process. • Usually obtained from the Choose • Choose an ‘object’ with its ‘certain Method property’. 3. Verify the particular ‘object’ has the ‘certain 3. Obtain a new statement in the backward property’ specified in the ‘for all’ statement. process. • Show that the chosen ‘object’ satisfy 4. Obtain a new statement in the forward ‘something happens’. process • ‘something happens’ for this particular ‘object’ 168

Exercise 3.29 March 2013 Q8, March 2015 Q9 Prove using the specialization method, that: If ������ is a subset of a set ������ of real numbers and if ������ and ������ are functions for which ������ ≥ ������ on ������, then ������ ≥ ������ on ������. Your answer should have an analysis of the proof only. [Hint: Suppose that ������ and ������ are functions of one variable. Then ������ ≥ ������ on the set ������ of real numbers if and only if for every element ������ ∈ ������, ������(������) ≥ ������(������).] 169

Exercise 3.30 September 2015 Q9 Prove the proposition using Specialization Method. For real numbers ������ and ������, prove that if ������ is an upper bound for a set ������ of real numbers and ������ ≤ ������ then ������ is an upper bound for ������. Your answer should have an analysis of proof. 170

Exercise 3.31 January 2018 Q7 Prove the following proposition using the Specialization Method. If ������ is a subset of a set ������ of real numbers and ������ is an upper bound for ������, then ������ is an upper bound for ������. Give the analysis of the proof and the condensed proof. [Hint: A real number ������ is an upper bound for a set ������ if for all elements ������ in ������, ������ ≤ ������] 171

3.7 The Contradiction Method Contradiction method is useful when the statement ������ contains ‘no’ or ‘not’. Contradiction Method I. Assume ������ is true. II. Assume ������ is not true, that is ������1 (¬������) and work forward to reach a contradiction. Example 3.15 If ������ is a real number such that ������y = 3 then ������ is irrational. Analysis of Proof: ������: ������ is a real number such that ������y = 3. ������: ������ is irrational. ������1: (¬������) ������ is rational. ������2: There are integers ������ and ������ with ������ ≠ 0 such that ������ = NO. ������3: ������ and ������ have no common divisor (that is, no integer divides both ������ and ������) ������4: ������y = ������y ������y ������5: 3 = ������y ������y ������6: 3������y = ������y ������7: 3 divides ������y ������8: 3 divides ������ ������9: ������ = 3������ for some integer ������ ������10: 3������y = (3������)y = 9������y = 3(3������y) ������11: ������y = 3������y ������12: 3 divides ������y A13: 3 divides ������ A14: 3 divides ������ and ������ (Contradicts with ������3) Condensed Proof: Assume to the contrary, that ������ is a rational number of the form ������ = N (where ������ and ������ are integers with O ������ ≠ 0) and that ������y = 3. Furthermore, it can be assumed that ������ and ������ have no common divisor. It follows that 3 = NOÑÑ, or equivalently 3������y = ������y. Since 3 divides ������y, it follows that 3 divides ������. Thus, there is an integer ������ such that ������ = 3������. Substitute ������, one obtains ������y = 3������y. From this, 3 divides ������y, so 3 divides ������. Thus, ������ and ������ have the common divisor 3, which cannot be. Hence, ������ is irrational. 172

Example 3.16 For any real number ������ and ������, if ������ is rational and ������ is irrational, then ������ − ������ is irrational. Analysis of Proof: ������: ������ is rational and ������ is irrational ������: ������ − ������ is irrational. ������1: ������ − ������ is rational. ������2: There are integers ������ and ������ with ������ ≠ 0 such that ������ − ������ = NO. ������3: There are integers ������ and ������ with ������ ≠ 0 such that ������ − ������ = óî. ������4: ������ − ������ = ������������ ������ ������ = ������ − ������������ ������ ������ = ������������ − ������������ ������������ ������5: ������ is rational. (Contradicts the hypothesis that ������ is irrational.) Condensed Proof: 173

Exercise 3.32 March 2012 Q9 Prove by the contradiction method: If ������ is a real number such that ������y = 2, then ������ is irrational. Your answer should have an analysis of proof only. 174

Exercise 3.33 September 2014 Q7 By using contradiction method, prove that X√2 is irrational. Your answer should have an analysis of proof only. 175

Exercise 3.34 September 2015 Q7 Prove the statement using Contradiction Method. If ������y − 9 ≥ 0 then ������ ≤ −3 or ������ ≥ 3. Your answer should have an analysis of proof. Exercise 3.35 March 2016 Q7 Prove the following statement using the Contradiction Method. There do not exist three consecutive odd integers ������, ������, and ������ such that ������y + ������y = ������y. Your answer should have an analysis of proof only. 176

Exercise 3.36 October 2016 Q7 Prove the following statement using the Contradiction Method. If ������ is a real number such that ������ ≠ 0, then the function ������(������) = ������ð is one-to-one. Your answer should have an analysis of proof only. [Hint: A function ������ of one variable is one-to-one if and only if, for all real numbers ������ and ������ with ������ ≠ ������, ������(������) ≠ ������(������)] Exercise 3.37 March 2017 Q8 Prove the proposition by Contradiction Method. If ������, ������, ������ are even numbers, then sum of them is even. Show analysis of proof only. 177

Exercise 3.38 January 2018 Q9 Prove the following using the Contradiction Method. If ������ ≥ 2 and ������ are integers, then ������ ∤ ������ or ������ ∤ (������ + 1). Show the analysis of proof only. Exercise 3.39 December 2018 Q7 Prove the proposition using contradiction method. If ������ is odd then ������y − 4������ ≠ 2. Show the analysis of proof only. 178

Exercise 3.40 June 2019 Q7 Prove the following proposition using the contradiction method. If ������ and ������ are integers and ������ is odd, then ±1 are not roots of ������������Ê + ������������y + ������ = 0. Show the analysis of proof only. 179

3.8 The Contrapositive Method This method is a type of proof by contradiction. It is useful to use this method when the statement in the backward process contains the word ‘no’ or ‘not’. Contrapositive Method I. Assume ������ and ¬������ are true. II. Work forward from ¬������ to obtain ¬������. III. Work backward from ¬������ to obtain ¬������. Example 3.17 Let ������ and ������ be real numbers, if ������ ≠ ������, then ������Ø ≠ ������Ù. Analysis of Proof: ������: ������ ≠ ������ ������: ������Ø ≠ ������Ù ������1: (¬������) ������Ø = ������Ù ������1: (¬������) ������ = ������ ������2: ������ = ln ������Ø and ������ = ln ������Ù ������3: ln ������Ø = ln ������Ù ������ ln ������ = ������ ln ������ ������ = ������ ������3 ⟺ ������1 Proof Complete Condensed Proof: Suppose by contrapositive, ������Ø ≠ ������Ù. Then by taking natural logarithm on both sides will yield, ln ������Ø = ln ������Ù. Simplifying the equation, one obtains ������ ln ������ = ������ ln ������. Thus, ������ = ������. 180

Example 3.18 If ������ and ������ are two integers whose product is odd, then both ������ and ������ must be odd. Analysis of Proof: ������: ������ and ������ are two integers whose product is odd. ������: Both ������ and ������ must be odd. ������1: (¬������) Either ������ is odd or ������ is odd. ������1: (¬������) ������ and ������ are two integers whose product is even. ������2: Let ������ be odd and ������ be even. ������3: ������ = 2������ + 1 and ������ = 2������, for some integers ������, ������. ������������ = (2������ + 1)(2������) = 4������������ + 2������ = 2(2������������ + ������) ������4: The product of ������ and ������ is even. ������4 ⟺ ������1 Proof Complete Condensed Proof: Let ������ be odd and ������ is even. Then there are some integers ������ and ������ such that ������ = 2������ + 1 and ������ = 2������. The product of ������ and ������ is ������������ = 2(2������������ + ������), hence ������������ is even. Therefore, by contrapositive, if the product of ������ and ������ is odd, then both ������ and ������ must be odd. 181

Exercise 3.41 March 2012 Q10(b) Prove by using the contrapositive method: If ������, ������ and ������ are integers for which ������ does not divide ������, then ������ does not divide ������ or ������ does not divide ������. Your answer should have the analysis and the condensed proofs. 182

Exercise 3.42 March 2013 Q9 Suppose that ������ and ������ are positive real numbers. Prove using the contrapositive method that: If √������������ ≠ ðyGj, then ������ ≠ ������ Your answer should have an analysis of the proof and the condensed proof. 183

Exercise 3.43 September 2013 Q7 Prove by the contrapositive method: If ������ + ������ is an odd integer then ������ is even or ������ is even. Your answer should have an analysis of the proof and the condensed proof. 184

Exercise 3.44 March 2014 Q9 Prove by the contrapositive method that: If ������, ������ ∈ ������ for which 3 does not divide ������������ , then 3 does not divide ������ or 3 does not divide ������. Your answer should have an analysis of the proof only. Exercise 3.45 September 2014 Q8(b) For the proposition: For any positive integers ������ and ������, if ������ − ������ is odd then either ������ is odd or ������ is odd. Fill in the blanks to complete the structure of the proof using contradiction and contrapositive method. Contradiction method: Assume that. ........................... then ........................... . Contrapositive method: Assume that. ........................... then ........................... . 185

Exercise 3.46 September 2015 Q8 Prove the proposition using the Contrapositive Method. If ������������ is an odd integer then ������ is an even integer and ������ is an odd integer. Your answer should have an analysis of the proof and the condensed proof. 186

Exercise 3.47 March 2016 Q8 Prove by the Contrapositive Method. If ������ is an odd integer then the equation ������y + ������ − ������ = 0 for ������ ∈ ������ has no solution for ������. Your answer should have an analysis of the proof and the condensed proof. 187

Exercise 3.48 October 2016 Q8 Prove by the Contrapositive Method. If ������ is an integer that is not a square such that ������ > 0 , then √������ is irrational. Your answer should have an analysis of the proof and the condensed proof. 188

Exercise 3.49 March 2017 Q9 Prove by using the Contrapositive Method. If ������ ∈ ������ and −2 < ������ < 2, then ������y < 4. Show the analysis of proof and condensed proof. 189

Exercise 3.50 January 2018 Q8 Prove using the Contrapositive Method. If ������k + 2������ + 1 is odd, then ������ is even. Show the analysis of proof only. 190

Exercise 3.51 December 2018 Q9 Prove using contrapositive method. Suppose ������, ������ ∈ ������, if 5 ∤ ������������, then 5 ∤ ������ and 5 ∤ ������. Show the analysis of proof and condensed proof. 191

Exercise 3.52 June 2019 Q6 Prove the following proposition using the contrapositive method. If ������ > 0 is an integer that is not a square, then √������ is irrational. Show the analysis of proof only. 192

3.9 The Induction Method Proving method for a special form of statement B that deals with the quantifier “for all”, specifically, B: For all integers ������ ≥ ������, ‘something happens’. The ‘something happens’ is some statement P(n), that depends on integer n. Consider the mathematical statement ∀������ ∈ ℤG, ������(������): j ������ = 1 + 2 + 3 + ⋯ + ������ = ������(������ + 1) 2 ú ûü¬ Then ������(������) Sigma Notation Expanded form Formula ������(1): ¬ 1 1(1 + 1) ������(2): 1 + 2 = ������(1) + 2 2 ������(3): ú ������ 1 + 2 + 3 = ������(2) + 3 ������(4): 1 + 2 + 3 + 4 = ������(3) + 4 2(2 + 1) ûü¬ 2 y 3(3 + 1) 2 ú ������ 4(4 + 1) ûü¬ 2 k ! ú ������ ûü¬ Ê ú ������ ûü¬ !! ! ������(������): ÿ 1 + 2 + 3 + 4 + ⋯ + ������ ������(������ + 1) ������(������ + 1): 2 ú ������ 1 + 2 + 3 + 4 + ⋯ + ������ + (������ + 1) = ������(������) + (������ + 1) (������ + 1)œ(������ + 1) + 1• ûü¬ 2 ÿG¬ ú ������ ûü¬ Note: ������ is some integer If we assume that the formula is true for ������ that is a large number (say ������ = 1000), then we can show that the formula is also true for the next integer (������ + 1 = 1001). Consequently, this shows that the statement ������(������) is true for infinite integers of ������. 193

Mathematical Induction When trying to prove ������(������) is true for all ������ ∈ ℤG by mathematical induction, you should: I. Verify that ������(1) is true. II. Assume that ������(������) is true, for some integer ������ ∈ ℤG. III. Use the assumption in Step II to show that ������(������ + 1) is true. Show that ������(������ + 1) = ������(������) + ������ÿG¬ where ������ÿG¬ is the (������ + 1)th term. Example 3.19 By using mathematical induction, prove that for all ������ ∈ ℤG j ú(2������ − 1) = 1 + 3 + 5 + ⋯ + (2������ − 1) = ������y ûü¬ Proof: Let ������(������): 1 + 3 + 5 + ⋯ + (2������ − 1) = ������y 1. Verify that ������(1) is true. ������(1): 2(1) − 1 = (1)y ������������������: 2(1) − 1 = 1 ������������������: (1)y = 1 Since ������������������ = ������������������, then ������(1) is true. 2. Assume that ������(������) is true. ������(������): 1 + 3 + 5 + ⋯ + (2������ − 1) = ������y 3. Show that ������(������ + 1) is true. ������(������ + 1): 1 + 3 + 5 + ⋯ + (2������ − 1) + (2(������ + 1) − 1) = (������ + 1)y ������������������: (������ + 1)y = (������ + 1)(������ + 1) = ������y + 2������ + 1 ������������������: 1 + 3 + 5 + ⋯ + (2������ − 1) + (2(������ + 1) − 1) = ������(������) + (2(������ + 1) − 1) = ������y + (2������ + 2 − 1) = ������y + 2������ + 1 Since ������������������ = ������������������, then ������(������ + 1) is true. Therefore, ������(������) is true for all positive integers ������ ∈ ℤG. 194


Like this book? You can publish your book online for free in a few minutes!
Create your own flipbook