More Proof TechniquesProof by ContradictionMethodPotential PitfallProof by CasesPredicatesQuantifying a PredicateMore Cryptic NotationMixing QuantifiersOrder of QuantifiersVariables over One DomainNegating QuantifiersValidityMathematical Data TypesSome Popular SetsComparing and Combining SetsComplement of A SetPower SetSequencesSet Builder NotationFunctionsDoes All This Really Work?Massachusetts Institute of Technology Course Notes, Week 2 6.042J/18.062J, Fall ’05: Mathematics for Computer Science September 12 Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised September 30, 2005, 562 minutes Predicates & Sets 1 More Proof Techniques 1.1 Proof by Contradiction In a proof by contradiction or indirect proof , you show that if a proposition were false, then some logical contradiction or absurdity would follow. Thus, the proposition must be true. So proof by contradiction would be described by the inference rule Rule. ¬ P −→ F P Proof by contradiction is always a viable approach. However, as the name suggests, indirect proofs can be a little convoluted. So direct proofs are generally preferable as a matter of clarity. 1.2 Method In order to prove a proposition P by contradiction: 1. Write, “We use proof by contradiction.” 2. Write, “Suppose P is false.” 3. Deduce a logical contradiction. 4. Write, “This is a contradiction. Therefore, P must be true.” Example Remember that a number is rational if it is equal to a ratio of integers. For example, 3.5 = 7/2 and 0.1111 . . . = 1/9 are rational numbers. On the other hand, we’ll prove by contradiction that √ 2 is irrational. Theorem 1.1. √ 2 is irrational. Copyright © 2005, Prof. Albert R. Meyer.2 Course Notes, Week 2: Predicates & Sets Proof. We use proof by contradiction. Suppose the claim is false; that is, √2 is rational. Then we can write √2 as a fraction a/b in lowest terms. 2Squaring both sides gives 2 = a2/b2 and so 2b2 = a . This implies that a is even; that is, a is a 2multiple of 2. Therefore, a2 must be a multiple of 4. Because of the equality 2b2 = a2, we know 2bmust also be a multiple of 4. This implies that b2 is even and so b must be even. But since a and b are both even, the fraction a/b is not in lowest terms. This is a contradiction. Therefore, √2 must be irrational. 1.3 Potential Pitfall Often students use an indirect proof when a direct proof would be simpler. Such proofs aren’t wrong; they just aren’t excellent. Let’s look at an example. A function f is strictly increasing if f(x) > f(y) for all real x and y such that x > y. Theorem 1.2. If f and g are strictly increasing functions, then f + g is a strictly increasing function. Let’s first look at a simple, direct proof. Proof. Let x and y be arbitrary real numbers such that x > y. Then: f(x) > f(y) (since f is strictly increasing) g(x) > g(y) (since g is strictly increasing) Adding these inequalities gives: f(x) + g(x) > f(y) + g(y) Thus, f + g is strictly increasing as well. Now we could prove the same theorem by contradiction, but this makes the argument needlessly convoluted. Proof. We use proof by contradiction. Suppose that f +g is not strictly increasing. Then there must exist real numbers x and y such that x > y, but f(x) + g(x) ≤ f(y) + g(y) This inequality can only hold if either f(x) ≤ f(y) or g(x) ≤ g(y). Either way, we have a contra-diction because both f and g were defined to be strictly increasing. Therefore, f + g must actually be strictly increasing.Course Notes, Week 2: Predicates & Sets 3 1.4 Proof by Cases In Week1 Notes we verified by truth table that the two expressions A ∨ (A ∧ B) and A ∨ B were equivalent. Another way to prove this would be to reason by cases: A is T. Then A ∨ anything will have truth value T. Since both expressions are of this form, in this case, both have the same truth value, namely, T. A is F. Then A ∨ P will have the same truth value as P for any proposition, P . So the second expression has the same truth value as B. Similarly, the first expression has the same truth value as F ∧ B which also has the same value as B. So in this case, both expressions will have the same truth value, namely, the value of B. Here’s a slightly more interesting example. Let’s agree that given any two people, either they have met or not. If every pair of people in a group has met, we’ll call the group a club. If every pair of people in a group has not met, we’ll call it a group of strangers. Theorem. Every collection of 6 people includes a club of 3 people or a group of 3 strangers. Proof. The proof is by case analysis1. Let x denote one of the six people. There are two cases: 1. Among the remaining 5 people, at least 3 have met x. 2. Among the remaining 5 people, at least 3 have not met x. We first argue that at least one of these two cases must hold.2 We’ll prove this by contradiction. Namely, suppose neither case holds. This means that at most 2 people in the group met x and at most 2 did not meet x. This leaves at least 1 of the remaining 5 people unaccounted for. That is, at least 1 of the people neither met x nor did not meet x, which contradicts our agreement that every pair has met or has not met. So at least one of these two cases must hold. Case 1: Suppose that at least 3 people that did meet x. This case splits into two subcases: Case 1.1: no pair among those people met each other. Then these people are a group of at least 3 strangers. So the Theorem holds in this subcase. Case 1.2: some pair among those people have met each other. Then that pair, together with x, form a club of 3 people. So the Theorem holds in this subcase. This implies that the Theorem holds in Case 1. Case 2: Suppose that there exist at least 3 people that did not meet x. This case also splits into two subcases: 1Describing your approach at the outset helps orient the reader. 2Part of a case analysis argument is showing that you’ve covered all the cases. Often this is trivial, because the two cases are of the form “P ” and “not P ”. However, the situation above is not s o simple.� 4 Course Notes, Week 2: Predicates & Sets Case 2.1: every pair among those people met each other. Then these people are a club of at least 3 people. So the Theorem holds in this subcase. Case 2.2: some pair among those people have not met each other. Then that pair, together with x, form a group of at least 3 strangers. So the
View Full Document
Unlocking...