A. On the nature of theorems ======================================================================== 1. We defined a formal logical proof as: a sequence of propositions such that each is either: * an axiom (a tautology) * a premise (sometimes also called an assumption or a postulate); i.e., a proposition accepted as true for the sake of the argument * or follows from previous propositions by a (valid) rule of inference where the last proposition is the conclusion Def: A _theorem_ is, by definition, the conclusion of a valid argument with no premises (only axioms) ------------------------------------------------------------------------ 2. An informal mathematical proof can also include definitions and previously proved theorems ( = "lemmas"); think of them as like sub-routines ------------------------------------------------------------------------ 3. Despite what the text says, although a theorem is a proposition "that can be shown to be true", that's not how "theorem" is defined. By definition, a theorem is the conclusion of a valid argument theorem =df last line of a proof therefore, a theorem can be shown to be T (but not all true propositions are provable --that's Goedel's Theorem!) And a proof does not "establish the truth of a theorem" Rather, it shows that the theorem can be validly derived from axioms i.e., it establishes the *relative truth* of the theorem -- its truth *relative to* the truth of the axioms And not all mathematicians accept all axioms! (e.g., not all of them accept the axiom of choice, which says that you can always choose a member from an infinite set) In general, the last line of a proof (with or w/o prems) is true only relative to the starting points (the axioms & premises) B. Strategies for Proofs ======================================================================== 1. A top-level strategy for proving a theorem is to look at its logical form and then use a lower-level strategy for proving statements of that form. Form of theorem Strategy ------------------------------------------------------------------------ a) P(x), where P(x) =df D(x) Show D(x) (i.e., suppose you have to prove that something has property P, where property P is defined in terms of some other property D) ------------------------------------------------------------------------ b) p -> q Assume (or suppose or make believe) that p, & then try to show that q This is called "direct proof" You can combine these: If p = P(x), and P(x) =df D(x), then to prove that p->q, suppose D(x) and then try to show q ------------------------------------------------------------------------ c) Ax[P(x) -> Q(x)] Choose some arbitrary c in the domain, and try to show P(c) -> Q(c) (e.g., by direct proof). Then use Universal Generalization to get the universal quantifier back. ------------------------------------------------------------------------ E.g.: Prove: If n is odd, then n+1 is even. Hidden assumption: n is an element of Z Form of proposition: An[Odd(n) -> Even(n+1)] Strategy: Let c be an integer Show Odd(c) -> Even(c+1) Assume Odd(c) & show Even(c+1) But Even(x) =df Ej[x=2j] So, show Ej[c+1=2j] By assumption, Odd(c) therefore, Ek[c=2k+1]; this is the definition of Odd(c) {note another strategy being used here: replace predicates by their definitions] therefore, show (2k+1)+1 is even (because c = 2k+1) Now do some arithmetic/algebra: (2k+1)+1 = 2k+2 = 2(k+1) -- these are lemmas from algebra therefore take j = k+1 i.e., Ej[c+1=2j], namely j=k+1 therefore, c+1 is even. QED 2. Form Strategy ------------------------------------------------------------------------ p -> q Try to show -q -> -p (which is logically equiv to p -> q) How? by previous strategy, namely: suppose -q & try to show -p This is called "proof by contraposition" or "indirect proof". Especially useful if q is "simpler" than p ------------------------------------------------------------------------ e.g., show: If 7n-5 is odd, then n is even strategy: show An[Odd(7n-5) -> Even(n)] Let c be an arbitrary integer, & show Odd(7c-5) -> Even(c). We *could* suppose that Odd(7c-5) & try to show Even(c). But *might* be easier to show: -Even(c) -> -Odd(7c-5): therefore, suppose -Even(c) & show -Odd(7c-5) i.e., supp. Odd(c) & show Even(7c-5) Note another strategy: Get rid of negations i.e., supp. c=2k+1 for some k, &show Ej[7c-5=2j] i.e., find j such that 7c-5=2j But we know that c=2k+1 therefore, 7c-5 = 7(2k+1)-5 = 14k+7-5 = 14k+2 = 2(7k+1) therefore, take j=7k+1 QED 3. When should you use direct proof & when should you use indirect proof? In p -> q,if q is simpler than p, then use indirect proof else try either method; if it goes nowhere, use the other! ------------------------------------------------------------------------ 4. More strategies Form Strategy ------------------------------------------------------------------------ F -> q "vacuous" proof: where "F" is any contradiction p -> q *must* be T! p -> T "trivial" proof: where "T" is any tautology p -> q *must* be T! 5. Proof by Contradiction: (another kind of indirect proof) (the "look under the street lamp where the light is better rather than across the street where you lost your keys in the dark alley" strategy) Form Strategy ------------------------------------------------------------------------ to show p Suppose -p & try to show Er[r ^ -r] i.e., find r such that r ^ -r Why? by truth table: -p -> (r ^ -r) is equiv to -p -> F so, tval(-p) = F (because -p -> F is assumed true) so, tval(p) = T ------------------------------------------------------------------------ famous e.g.: Show sqrt(2) is irrational (p): Supp. sqrt(2) *is* rational (-p) & show Er[r ^ -r]: Supposing sqrt(2) is ratioal, we know there must be integers a,b such that sqrt(2) = a/b, a fraction in lowest terms i.e., a, b have no common factors (this will turn out to be "-r") because sqrt(2) = a/b, we have 2 = (a^2)/(b^2) so, 2b^2 = a^2 so, a^2 is even so, a is even (this is a lemma; see exercise 16 in text) so, Ec[a=2c]; call this constant c1 so, 2b^2 = (2*c1)^2 = 4*(c1)^2 so, b^2 = 2*(c1)^2 so, b is even so, a and b *do* have a common factor, namely, 2; this is "r" QED 6. Form Strategy ------------------------------------------------------------------------ to prove p -> q Supp. p supp. -q show Er[r ^ -r] This is another form of proof by contradiction It works, because the previous strategy for p->q is: supp p & show q but a previous strategy to show q was to supp -q and show a contradiction. This just combines them. ------------------------------------------------------------------------ 7. to prove p <-> q show p -> q & show q -> p (this is an instance of the definitional strategy from earlier) ------------------------------------------------------------------------ 8. To prove p1 <-> p2 <-> ... <-> p-n: show p1->p2 & p2->p3 &...& & p-n -> p1 You could also try to show that all possible pairs of biconditionals are the case, but this strategy is a lot easier! Application: Church-Turing thesis: Turing machines <-> lambda calculus <-> Post production systems <-> Markov algorithms, etc. ------------------------------------------------------------------------ 9. to show -AxP(x) Find a counterexample i.e. show Ex-P(x) 10. There are lots of ways to have *invalid* arguments (see text, pp.83-84) More importantly: it's possible that there are *invalid* arguments with *true* conclusions! That doesn't make the arguent valid. And it doesn't prove the conclusion! E.g.: All birds fly. Tweety the canary flies. So, Tweety is a bird. This has true premises and a true conclusion, but is an invalid argument. Sect 1.7: More Pf Methods & Strategies ======================================================================== 1. Proof by Cases Form of theorem to be proved: Strategies ------------------------------------------------------------------------ (P1 v ... v Pn) -> Q Show P1 -> Q ... Show Pn -> Q Justification of this strategy: (P1 v ... v Pn) -> Q is logically equiv to (P1 -> Q) ^...^ (Pn -> Q) Note the switch from "v" to "^". This logical equivalence cannot be proved *by us* *yet*: we'll need "mathematical induction" (the last Peano Axiom) to do that But note that: (P1 v P2) -> Q is logically equivalent to (P1 -> Q) ^ (P2 -> Q) (you can do a quick truth table to convince yourself of this, or you can suppose that tval(LHS) = F and tval(RHS) = T and work backward to derive contradictory tvals for atomic propositions) ------------------------------------------------------------------------ But there is sometimes a trick in applying this, because the antecedent of a theorem might not look as though it's a disjunction: e.g.: Theorem: If n is an integer, then n^2 >= n Note that "n is an integer" is logically equivalent to: n<0 v n=0 v n>0 So, to show (n is an integer) -> (n^2 >= n), we only have to show: (n<0 v n=0 v n>0) -> (n^2 >= n) and this has the form of a proof by cases. So, showing that complicated proposition reduces to showing 3 simpler ones: (a) (n<0) -> (n^2 >= n) and (b) (n=0) -> (n^2 >= n) and (c) (n>0) -> (n^2 >= n) Case (a): Supp n<0 & show n^2 >= n: Because n<0, we have n^2 > 0 (the product of 2 negatives is positive) But n<0 implies 0>n, so 0 >=n (by Addition!) so n^2 > 0 and 0 >= n so n^2 >= n Case (b): Supp n=0 & show n^2 >= n: Because n=0, we have n^2=0, so n^2=n (because they're both = 0) so n^2 >= n (by Addition) Case (c): Supp n>0 & show n^2 >= n: Because n>0, we have n^2 > 0, but that doesn't seem to get us anywhere :-( So, try this: Because n>0, n >= 1 So, n*n >= 1*n (multiplying both sides by n) So, n^2 >= n (Case (c) is a nice example of a tricky proof where it's more important for you to understand the proof than it is to worry about how you would have come up with the trick at the end.) QED 2. Existence Pfs Form Strategy ------------------------------------------------------------------------ ExP(x) (a) Constructive: Find c such that P(c) Then use existential generalization (b) Non-Constructive: e.g.: Use proof by contradiction: Supp -ExP(x) & try to derive a contra. or: Show Er[(r v -r) -> ExP(x)] e.g.: Theorem: ExEy[Irrational(x) ^ Irrational(y) ^ Rational(x sup y)] (where "x sup y" = x raised to the y power) i.e., there are 2 irrational numbers such that when one is raised to the power of the other, the result is rational (!!) Let's restate this in a slightly more helpful way, where Q(x) = x is rational ExEy[-Q(x) ^ -Q(y) ^ Q(x sup y)] proof: Strategy: Find x,y not in Q such that x sup y is in Q Try x = y = sqrt(2). Note that sqrt(2) is not in Q, i.e., -Q(sqrt(2)) (by earlier proof) Consider sqrt(2) sup sqrt(2): For convenience in these notes, call it N Either Q(N) or -Q(N). Supp Q(N). Then we're done! We've found our x and y! Namely, x = y = sqrt(2). Supp -Q(N). Then consider N sup sqrt(2), i.e., [sqrt(2) sup sqrt(2)] sup sqrt(2) Note that -Q(N) (by hypothesis) and -Q(sqrt(2)) by earlier proof. Could it be possible that N sup sqrt(2) is rational? N sup sqrt(2) = sqrt(2) sup [sqrt(2) * sqrt(2)], by laws of exponents = sqrt(2) sup 2, by arithmetic = 2 and indeed Q(2), so we're done! Namely, x = N and y = sqrt(2). But which is it? WE DON'T KNOW!! But one of them works, and that's all that we were asked to prove! QED This is an example of a non-constructive proof, because we didn't really find ("construct") the answer; we merely showed that there was an answer. Not all mathematicians or computer scientists accept non-constructive proofs 3. There are lots of other strategies and variations; we'll introduce them as we need them. ------------------------------------------------------------------------ 4. Can *any* old proposition (or its negation) be proved? NO! a) There are propositions whose truth value we don't know *yet* * Up till a few years ago, Fermat's Last Theorem had not been proved: "x sup n + y sup n = z sup n has no solutions for integers x,y,z and integer n>2" but fairly recently it was proved * Goldbach's conjecture: All positive even integers are the sum of 2 primes i.e.,: Ax[(Z(x) ^ (x>0) ^ Even(x)) -> EyEz[Prime(y) ^ Prime(z) ^ x=y+z]] e.g., 28 = 5 + 23 This has not (yet) been proved or disproved! * Twin Prime Conjecture: There are an infinite number of twin primes, i.e., primes m,n such that n=m+2 i.e., AmAn[(Prime(m) ^ Prime(n) ^ n=m+2) -> ExEy[Prime(x) ^ Prime(y) ^ y=x+2 ^ y>m ^ x>n]] This has not (yet) been proved or disproved! b) There are propositions whose truth value we *know* but cannot prove! Goedel's Incompleteness Theorem: Here's a highly simplified version of it: "This proposition is unprovable" is a true proposition that is unprovable (!) And here's a highly simplified version of its proof: Suppose the quoted proposition is false. Then it is false that it is unprovable. Therefore, it is provable. But all provable propositions are true Therefore, it is true that it is unprovable. Therefore, it is both true and unprovable. Cf. Shakespeare: There are more things [that are true] in heaven and earth than are dreamt of in your philosophy [i.e., that can be proved by your logic] :-)