2. Preliminary Concepts - Indirect Proofs 2.pdf

MATH104 – Abstract Algebra First Semester A.Y. 2021-2022 MODULE 2 - PRELIMINARY CONCEPTS: INDIRECT PROOFS I. Topics Indirect Proofs II. Learning Objectives At the end of this module, th...

MATH104 – Abstract Algebra First Semester A.Y. 2021-2022 MODULE 2 - PRELIMINARY CONCEPTS: INDIRECT PROOFS I. Topics Indirect Proofs II. Learning Objectives At the end of this module, the students will be able to: define and contrast the method of indirect from other kinds of proof; and prove mathematical statement by indirect proof. III. Content 2.1 Indirect Proofs Proofs make use of an axiom, a postulate, a previously proven theorem or any allowable construction. There are two kinds of proofs; the direct proof and the indirect proof. The method by indirect proof is sometimes called the proof of contradiction. The indirect proof is basically done by assuming the conclusion to be false and then in the process of arguments it leads to a certain contradiction, that is, contradicting the hypothesis, or may be some contradictory result arises. The steps to follow when proving indirectly are: Assume the opposite of the conclusion (second half) of the statement. Proceed as if this assumption is true to find the contradiction. Once there is a contradiction, the original statement is true. DO NOT use specific examples. Use variables so that the contradiction can be generalized. Example 2.1 (Recall) Prove the proposition using direct proof. 2 Proposition: “If 𝑥 is an odd integer, then 𝑥 is an odd integer.” Know Reason P 𝑥 is an odd integer (Assuming hypothesis is true) 𝑝∈𝑍, 𝑥 = 2𝑝 + 1 Definition of odd integer 2 2 𝑥 = (2𝑝 + 1) 2 = 4𝑝 + 4𝑝 + 1 2 Algebra ( = 2 2𝑝 + 𝑝 + 1 2 ) 𝐿𝑒𝑡 2𝑝 + 𝑝 = 𝑞 2 𝑞∈𝑍, 𝑥 = 2𝑞 + 1 Definition of odd integer 2 Q ∴𝑥 is an odd integer Show 2 Thus, it has been proven that “If 𝑥 is an odd integer, then 𝑥 is an odd integer.” Example 2.2 Prove the proposition using indirect proof. Proposition: “If the square of an integer n is even, then n itself is even.” Solution: Know Reason 2 P 𝑛 is an even integer (Assuming hypothesis is true) 2 𝑝 ∈ 𝑍, 𝑛 = 2𝑝 Definition of even integer 𝑝, 𝑞 ∈ 𝑍, 2 𝑛 = 2𝑝 ≠ 2𝑞 + 1 2 2 𝑛 = (2𝑘 + 1) 2 = 4𝑘 + 4𝑘 + 1 2 = 2(2𝑘 + 2𝑘) + 1 Algebra 2 𝐿𝑒𝑡 2𝑘 + 2𝑘 = 𝑞 ∈ 𝑍 2 𝑛 = 2𝑞 + 1 𝑘 ∈ 𝑍, 𝑛 = 2𝑘 + 1 Definition of odd integer ~Q ∴ n is an odd integer (Assumption) Show  2 “𝑛 = 2𝑝 ≠ 2𝑞 + 1” gives a contradiction to the hypothesis. Thus, the assumption is false and so the conclusion is true. Example 2.3 Prove the proposition using indirect proof. 2 Proposition: “If 𝑥 is an odd integer, then 𝑥 is an odd integer.” Solution: Know Reason P 𝑥 is an odd integer (Assuming hypothesis is true) 𝑝∈𝑍, 𝑥 = 2𝑝 + 1 Definition of odd integer 2 2 𝑥 = (2𝑝 + 1) 2 = 4𝑝 + 4𝑝 + 1 2 = 2(2𝑝 + 2𝑝) + 1 Algebra 2 𝐿𝑒𝑡 2𝑝 + 2𝑝 = 𝑞 ∈ 𝑍 2 𝑥 = 2𝑞 + 1 2 𝑞, 𝑟∈𝑍, 𝑥 = 2𝑞 + 1 ≠ 2𝑟 2 𝑟 ∈ 𝑍, 𝑥 = 2𝑟 Definition of odd integer 2 ~Q ∴ 𝑥 is an even integer (Assumption) Show 2 “𝑥 = 2𝑞 + 1 ≠ 2𝑟” gives a contradiction to the hypothesis. Thus, the assumption is false and so the conclusion is true. Example 2.4 Prove the proposition using indirect proof. Proposition: “If 𝑥 and 𝑦 are odd integers, then their sum is an even integer.” Solution: Know Reason P 𝑥 𝑎𝑛𝑑 𝑦 are odd integers (Assuming hypothesis is true) 𝑝∈𝑍, 𝑥 = 2𝑝 + 1 Definition of odd integer 𝑞∈𝑍, 𝑥 = 2𝑞 + 1 𝑥 + 𝑦 = (2𝑝 + 1) + (2𝑞 + 1) = 2𝑝 + 1 + 2𝑞 + 1 Algebra = 2𝑝 + 2𝑞 + 2  = 2(𝑝 + 𝑞 + 1) 𝐿𝑒𝑡 (𝑝 + 𝑞 + 1) = 𝑟 ∈ 𝑍 “ 𝑥 + 𝑦 = 2𝑟 𝑘, 𝑟∈𝑍, 𝑥 + 𝑦 = 2𝑟 ≠ 2𝑘 + 1 𝑥 + 𝑦 = 2𝑘 + 1, where 𝑘∈𝑍 Definition of odd integer ~Q ∴ 𝑥 + 𝑦 is an odd integer (Assumption) Show 𝑥 + 𝑦 = 2𝑟 ≠ 2𝑘 + 1” gives a contradiction to the hypothesis. Thus, the assumption is false and so the conclusion is true. Example 2.5 Prove the proposition using indirect proof. Proposition: “ 2 is an irrational number.” Solution: Know Reason P 2 is a rational number (Assuming hypothesis is true) 𝑎 “ 2= 𝑏 , where 𝑏 is positive, and 𝑎 and 𝑏 are integers that Definition of rational numbers have no common divisor in standard form other than 1. 2 𝑎 2 ( 2) = ( ) 𝑏 2 𝑎 2= 2 Algebra 𝑏 2 2 𝑎 = 2𝑏 2 2 If 𝑏 = 𝑚, then 𝑚 ∈ 𝑍, 𝑎 = 2𝑚 Definition of even integer and 𝑘 ∈ 𝑍, 𝑎 = 2𝑘 Proof: Example 2.2 2 2 (2𝑘) = 2𝑏 2 2 4𝑘 = 2𝑏 Algebra 2 2 2𝑘 = 𝑏 2 2 If 𝑘 = 𝑛, then 𝑛 ∈ 𝑍, 𝑏 = 2𝑛 Definition of even integer and 𝑞 ∈ 𝑍, 𝑏 = 2𝑞 Proof: Example 2.2 ~Q 𝑞 ∈ 𝑍, 𝑏 = 2𝑞 + 1 Definition of odd integer Show 𝑏 = 2𝑞≠2𝑞 + 1" gives a contradiction to the hypothesis. Thus, the assumption is false and 2 is a rational number. References Sergio E. Ymas Jr. (2012) Abstract Algebra (Modern Algebra): 2012 Edition. Sta. Monica Printing Corporation Susana S. Epp, Discrete Mathematics, Cengage Learning Asia Pte LTD, 2012 Kenneth H. Rosen, Discrete Mathematics and Its Application, Sixth Edition, McGraw-Hill Companies, Inc., 2008\ Maria Catherine Borres, Methods of Matrix Algebra, Arcler Press, 2018 IV. Self-Test Answer the following questions (3-5 sentences). 1. What are the key points in the module? ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ 2. Based on your readings, how can you apply the content from this module to your daily life? ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________