Direct Proof & Counterexample: Introduction

Tom Kelliher, MA 115

Oct. 8, 1997

Announcements

Assignment

1. Read 3.2.

2. Homework problems from 3.1, due 10/15: 7, 16, 24, 28, 34, and 43.

Introduction

Proofs:

1. Difficulties:
   1. Remembering definitions.

   2. Finding your way in the ``maze.''

   3. Taking small steps --- filling in the details.

2. Importance:
   1. Sharpening analytical and creative skills.

   2. Confidence in applying an idea to all possible cases. (``Proof by example.'')

Foundation from which we begin:

1. Basic algebra --- Appendix A.

2. Closure of integers under addition, subtraction, and multiplication. What about division???

Some Definitions

Even, Odd

For n an integer.

Even:

Odd:

Examples:

1. Is 6m + 8n even or odd?

2. Is 10mn + 7 even or odd?

Prime, Composite

For n an integer that is greater than 1.

Prime:

Composite:

Examples:

1. if r and s are both positive integers, is composite?

2. if m > n > 0, is composite?

Universal Proofs

(Existential proofs aren't unimportant.)

1. Method of generalizing from the generic particular.

2. Method of direct proof:
   1. Mentally, express the statement to be proved in the form

      

   2. Start by assuming that x is a particular, but arbitrarily chosen, member of D for which is true.

   3. Show that is true (the hard part).

3. Proof writing guidelines:
   1. Write the theorem to be proved.

   2. Clearly mark the beginning of the proof: Proof.

   3. Make the proof self-contained.

   4. Take small steps; justify each step.

   5. Write in English.

   6. Finish with Q.E.D.

Examples

1. Prove that the difference of two even integers is even.

2. Prove that the difference of an even and an odd integer is odd.

3. Prove that the product of any four consecutive integers is one less than a perfect square.

Other Proof ``Techniques''

These are for laughs only. If I see you using these...

1. Proof by example: The author gives only the case n = 2 and suggests that it contains most of the ideas of the general proof.

2. Proof by intimidation: ``Trivial'' or ``obvious.''

3. Proof by exhaustion: An issue or two of a journal devoted to your proof is useful.

4. Proof by omission: ``The reader may easily supply the details'', ``The other 253 cases are analogous''

5. Proof by obfuscation: A long plotless sequence of true and/or meaningless syntactically related statements.

6. Proof by wishful citation: The author cites the negation, converse, or generalization of a theorem from the literature to support his claims.

7. Proof by funding: How could three different government agencies be wrong? Or, to play the game a different way: how could anything funded by those bozos be correct?

8. Proof by democracy: A lot of people believe it's true: how could they all be wrong?

9. Proof by market economics: Mine is the only theory on the market that will handle the data.

10. Proof by eminent authority: ``I saw Ruzena in the elevator and she said that was tried in the 70's and doesn't work."

11. Proof by cosmology: The negation of the proposition is unimaginable or meaningless. Popular for proofs of the existence of God and for proofs that computers cannot think.

12. Proof by personal communication: ``Eight-dimensional colored cycle stripping is NP-complete [Karp, personal communication].''

13. Proof by reference to talk: ``At the special NSA workshop on computer vision, Binford proved that SHGC's could be recognized in polynomial time.''

14. Proof by reduction to the wrong problem: ``To see that infinite-dimensional colored cycle stripping is decidable, we reduce it to the halting problem.''

15. Proof by reference to inaccessible literature: The author cites a simple corollary of a theorem to be found in a privately circulated memoir of the Icelandic Philological Society, 1883. This works even better if the paper has never been translated from the original Icelandic.

16. Proof by ghost reference: Nothing even remotely resembling the cited theorem appears in the reference given. Works well in combination with proof by reference to inaccessible literature.

17. Proof by forward reference Reference is usually to a forthcoming paper of the author, which is often not as forthcoming as at first.

18. Proof by importance: A large body of useful consequences all follow from the proposition in question.

19. Proof by accumulated evidence: Long and diligent search has not revealed a counterexample.

20. Proof by mutual reference: In reference A, Theorem 5 is said to follow from Theorem 3 in reference B, which is shown to follow from Corollary 6.2 in reference C, which is an easy consequence of Theorem 5 in reference A.

21. Proof by metaproof: A method is given to construct the desired proof. The correctness of the method is proved by any of these techniques. A strong background in programming language semantics will help here.

22. Proof by picture: A more convincing form of proof by example. Combines well with proof by omission.

23. Proof by flashy graphics: A moving sequence of shaded, 3D color models will convince anyone that your object recognition algorithm works. An SGI workstation is helpful here.

24. Proof by misleading or uninterpretable graphs: Almost any curve can be made to look like the desired result by suitable transformation of the variables and manipulation of the axis scales. Common in experimental work.

25. Proof by vehement assertion: It is useful to have some kind of authority relation to the audience, so this is particularly useful in classroom settings.

26. Proof by repetition: Otherwise known as the Bellman's proof: ``What I say three times is true.''

27. Proof by appeal to intuition: Cloud-shaped drawings frequently help here.

28. Proof by vigorous handwaving: Works well in a classroom, seminar, or workshop setting.

29. Proof by semantic shift: Some of the standard but inconvenient definitions are changed for the statement of the result.

30. Proof by cumbersome notation: Best done with access to at least four alphabets, special symbols, and the newest release of LaTeX.

31. Proof by abstract nonsense: A version of proof by intimidation. The author uses terms or theorems from advanced mathematics which look impressive but are only tangentially related to the problem at hand. A few integrals here, a few exact sequences there, and who will know if you really had a proof?

32. Disproof by finding a bad apple: One bad apple spoils the whole bunch. Among the many proponents of this theory, we have found one who is obviously loony; so we can discredit the entire theory. (Often used in political contexts.)

33. Disproof by slippery slope (or thin end of wedge, if you are British): If we accepted [original proposal], we'd have to accept [slightly modified proposal], and eventually this would lead to [radically different and clearly objectionable proposal].

34. Disproof by ``not invented here'': We have years of experience with this equipment at MIT and we have never observed that effect.