Definition 2. An indirect method of a statement R by the method of contra- diction uses the logic that if R can't be false, then R must be true, that is using the tautology ~ R = R, where means a contradiction. PROOF OF R BY CONTRADICTION Proof. Assume ~ R. Therefore, S. Therefore, ~ S. Hence, SA ~ S a contradiction. Thus, R. Note 1: This method of proof can be applied to any proposition R, whereas direct proofs and proofs by contraposition can be used only for conditional sentences. Note 2: The strategy of proving R by proving ~ R (SA ~ S) has the disadvantage that when we set out to prove R, we may have no idea that what proposition to use as S. This means a proof by contradiction may require a spark of insight to determine a useful S. The advantage of this method is that there may be many propositions S such that ~ R implies both S and ~ S, and any such proposition may be used to construct the proof. 4.8 Indirect Argument: Two Classical Theorems Euclid's Lemma. Let a, b, and p be integers. If p is a prime and p divides ab, then p divides a or p divides b. HW for 4.7 : 1. Carefully formulate the negation of the following statement. Then prove the statement by contradiction: There is no greatest negative real number. 2. Prove that for all integers a, b and , if a|b and a fc then a f(b+ c). Prove each of the statements in two ways: (a) by contraposition and (b) by contra- diction. 3. For every integer n , if n? is odd then n is odd. 4. For all integers a, b and , if a fbe then a fb. HW for 4.8 : Determine which statements are true and which are false. Prove those that are true and disprove those that are false. 1. 8 5/2 is irrational. 2. The difference of any two irrational numbers is irrational. 3. If r is any rational number and s is any irrational number, then /s is irrational