MATH 211 Lecture Chapter 1 ( Section 1.6), Fall 2011

Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Introduction to proofs, Proof methods and strategies S. Abu Diab Mathematics Department American University of Beirut October 4, 2010 S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Outline 1 Introduction Why a Proof? Claims and Validity What is a Proof? 2 Methods of Proof Direct Proofs Indirect Proofs 3 Strategies of Proof Forward and Backward Reasoning Proof by Cases Exhausting Cases Adapting Existing Proofs Existence Proofs Constructive and Nonconstructive Proofs Others S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Why a Proof? Claims and Validity What is a Proof? Motivation Man has always made claims about all that surrounds him (people, nature, oneself,...) But not all of these claims come to work when implemented. In fact, we are ”bombarded” with claims in our everyday life. Advertisements, conversations, television shows, ... all present opinions that need to be checked and can not be taken for granted. We have seen that Logic (from Classical Greek logos (λ´oγoς)) is the study of the principles of valid inference and demonstration. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Why a Proof? Claims and Validity What is a Proof? Mathematical proofs use the rules of logical deduction that grew out of the work of Aristotle around 350 BC. We follow these rules instinctively. We understand them even when we do not say them. But they are formulated as a set of rules. This is how you check your reasoning!! S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Why a Proof? Claims and Validity What is a Proof? Axiom An axiom or postulate is a statement that is assumed to be true. (based on underlying assumptions about mathematical structures) Theorem A theorem is a statement that can be shown to be true. In mathematical writing, the term theorem is usually reserved for a statement that is considered somewhat important. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Why a Proof? Claims and Validity What is a Proof? Proof A proof is a sequence of statements that uses the rules of inference to reach the conclusion of the theorem. Or Proof A proof is a valid argument that establishes the truth of a mathematical statement. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Why a Proof? Claims and Validity What is a Proof? Lemma A lemma is a simple theorem used in the proof of other theorems. Proposition A proposition is a theorem that can be proved in few statements. Corollary A corollary is a proposition that can be proved directly from a given theorem. Conjecture A conjecture is a statement whose truth value is unknown. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Direct Proofs Indirect Proofs ”tout droit” start from the given and reach the conclusion. Example 1: Show that if n is an odd integer then n2 is an odd integer. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Direct Proofs Indirect Proofs Indirect = Not direct :) Indirect Proofs - Proofs by contraposition S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Direct Proofs Indirect Proofs Indirect = Not direct :) Indirect Proofs - Proofs by contraposition - Proofs by contradiction S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Direct Proofs Indirect Proofs Proof by contraposition: Instead of proving that p implies q, we prove that ¬q implies ¬p. Example 2: Show that if n is an integer and n2 is odd then n is odd. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Direct Proofs Indirect Proofs Proof by contradiction: We suppose that what you want to reach is false and get a contradiction. Example 3: Show that √ 2 is irrational. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Direct Proofs Indirect Proofs Proving an equivalence: two implications Counterexamples: to prove that a statement of the form ∀x P(x) is FALSE. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Forward and Backward Reasoning Proof by Cases Exhausting Cases Adapting Existing Proofs Existence Proofs Constructive and Nonconstructive Proofs Others You always need a starting point for your proof. To begin a direct proof for an implication, you can start with the hypotheses. Using the hypotheses, together with axioms and known theorems, you can construct a proof by a sequence of steps that leads to the conclusion. This type of reasoning, called forward reasoning is the most common way to reach relatively simple results. Similarly, with indirect proofs you will start with the negation of your conclusion and using a sequence of steps reach the negation of your assumption. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Forward and Backward Reasoning Proof by Cases Exhausting Cases Adapting Existing Proofs Existence Proofs Constructive and Nonconstructive Proofs Others However, it may be sometimes helpful to use backward reasoning. This means that we find a new conclusion that will lead to the original one and try to prove this new conclusion. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Forward and Backward Reasoning Proof by Cases Exhausting Cases Adapting Existing Proofs Existence Proofs Constructive and Nonconstructive Proofs Others Example 4: Show that the arithmetic mean of two different positive real numbers is always greater than their geometric mean, i.e., for any a, b ∈ R a + b 2 > √ ab If you think you know this, try showing that if a and b are distinct positive numbers, and A = a+b 2 , B = √ ab, then we have this inequality B < (a − b)2 8(A − B) < A S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Forward and Backward Reasoning Proof by Cases Exhausting Cases Adapting Existing Proofs Existence Proofs Constructive and Nonconstructive Proofs Others We consider all possible cases and prove each one alone. Example 5: Show that if |xy| = |x| |y| for any two real numbers x and y. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Forward and Backward Reasoning Proof by Cases Exhausting Cases Adapting Existing Proofs Existence Proofs Constructive and Nonconstructive Proofs Others Exhausting cases means you consider all possible single examples. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Forward and Backward Reasoning Proof by Cases Exhausting Cases Adapting Existing Proofs Existence Proofs Constructive and Nonconstructive Proofs Others Euclid showed that there are infinitely many primes by supposing that there are only finitely many primes p1, p2,..., pn. Then, considering the number p1p2p3...pn + 1. This is not divisible by any of the existing primes. Thus, it must be a prime. Example 6: Adapt Euclid’s proof that there are infinitely many primes to show that there are infinitely many primes of the form 4k + 3 where k is a nonnegative integer. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Forward and Backward Reasoning Proof by Cases Exhausting Cases Adapting Existing Proofs Existence Proofs Constructive and Nonconstructive Proofs Others This is when you show that ∃x P(x). S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Forward and Backward Reasoning Proof by Cases Exhausting Cases Adapting Existing Proofs Existence Proofs Constructive and Nonconstructive Proofs Others A proof is constructive if you construct the answer. For instance, you show that ∃x P(x)by finding this x. Otherwise, it is nonconstructive. Refer to page 91 S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References Forward and Backward Reasoning Proof by Cases Exhausting Cases Adapting Existing Proofs Existence Proofs Constructive and Nonconstructive Proofs Others Many other strategies exist. In fact, it is hard to track the creative process in an individual’s mind! S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References As you noticed, you can never do a proof if you do not know the definitions. Keep in mind the different ideas that are used in doing a proof. Always try to establish a link between your hypothesis and your conclusion. This link will be the bridge that you will use to reach the end result. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References When you want to prove a statement, be aware of the psychological factor. You can never achieve something if in your mind you believe that you can not do it. In proving non obvious statements, there is a creative factor sometimes. S. Abu Diab Introduction to proofs, Proof methods and strategies Introduction Methods of Proof Strategies of Proof Ready? Tips and Tricks References K. H. Rosen. Discrete Mathematics and its Applications. McGraw-Hill, 5th edition, 2003. S. Abu Diab Introduction to proofs, Proof methods and strategies