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 26.042J/18.062J, Fall ’05: Mathematics for Computer Science September 12Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld revised September 30, 2005, 562 minutesPredicates & Sets1 More Proof Techniques1.1 Proof by ContradictionIn a proof by contradiction or indirect proof, you show that if a proposition were false, then somelogical contradiction or absurdity would follow. Thus, the proposition must be true. So proof bycontradiction would be described by the inference ruleRule.¬P −→ FPProof by contradiction is always a viable approach. However, as the name suggests, indirect proofscan be a little convoluted. So direct proofs are generally preferable as a matter of clarity.1.2 MethodIn 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.”ExampleRemember that a number is rational if it is equal to a ratio of integers. For example, 3.5 = 7/2 and0.1111 . . . = 1/9 are rational numbers. On the other hand, we’ll prove by contradiction that√2 isirrational.Theorem 1.1.√2 is irrational.Copyright © 2005, Prof. Albert R. Meyer. All rights reserved.2 Course Notes, Week 2: Predicates & SetsProof. We use proof by contradiction. Suppose the claim is false; that is,√2 is rational. Then wecan write√2 as a fraction a/b in lowest terms.Squaring both sides gives 2 = a2/b2and so 2b2= a2. This implies that a is even; that is, a is amultiple of 2. Therefore, a2must be a multiple of 4. Because of the equality 2b2= a2, we know 2b2must also be a multiple of 4. This implies that b2is even and so b must be even. But since a and bare both even, the fraction a/b is not in lowest terms.This is a contradiction. Therefore,√2 must be irrational.1.3 Potential PitfallOften students use an indirect proof when a direct proof would be simpler. Such proofs aren’twrong; they just aren’t excellent. Let’s look at an example. A function f is strictly increasing iff(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 needlesslyconvoluted.Proof. We use proof by contradiction. Suppose that f +g is not strictly increasing. Then there mustexist real numbers x and y such that x > y, butf(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 actuallybe strictly increasing.Course Notes, Week 2: Predicates & Sets 31.4 Proof by CasesIn Week1 Notes we verified by truth table that the two expressions A ∨ (A ∧ B) and A ∨ B wereequivalent. 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 thiscase, 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 secondexpression has the same truth value as B. Similarly, the first expression has the same truthvalue as F ∧ B which also has the same value as B. So in this case, both expressions willhave 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 havemet or not. If every pair of people in a group has met, we’ll call the group a club. If every pair ofpeople 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.2We’ll prove this by contradiction.Namely, suppose neither case holds. This means that at most 2 people in the group met x and atmost 2 did not meet x. This leaves at least 1 of the remaining 5 people unaccounted for. That is, atleast 1 of the people neither met x nor did not meet x, which contradicts our agreement that everypair 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 groupof 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, togetherwith 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 twocases are of the form “P ” and “not P ”. However, the situation above is not so simple.4 Course Notes, Week 2: Predicates & SetsCase 2.1: every pair among those people met each other. Then these people are a clubof 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 Theorem holds in thissubcase.This implies that the Theorem also holds in Case 2, and therefore holds in all cases.2 PredicatesA predicate is a proposition whose
View Full Document
Unlocking...