FOCUS A
Proof Strategies
Mathematicians are sceptical people. They use many methods, including experimentation with examples, trial and error, and guesswork, to tiy to find answers to mathematical questions, but they are generally not convinced that an answer is correct unless they can prove it.
Proofs are a lot like jigsaw puzzles. There are no rules about how jigsaw puzzles must be solved. The only rule concerns the final product: All the pieces must fit together, and the picture must look right. The same holds for proofs.
Some techniques for solving jigsaw puzzles work better than others. For example, you'd never do a jigsaw puzzle by filling in every other piece, and then going back and filling in the holes! But you also don't do it by starting at the top and filling in the pieces in order until you reach the bottom. You probably fill in the border first, and then gradually put other chunks of the puzzle together and figure out where they go. Sometimes you try to put pieces in the wrong places, realise that they don't fit, and feel that you're not making any progress. And every once in a while you see, in a satisfying flash, how two big chunks fit together and feel that you've suddenly made a lot of progress. As the pieces of the puzzle fall into place, a picture emerges. You suddenly realise that the patch of blue you've been putting together is a lake, or part of the sky. But it's only when the puzzle is complete that you can see the whole picture.
Similar things could be said about the process of figuring out a proof. And we will discuss the proof-writing techniques that mathematicians use most often and explain how to use them to begin writing proofs yourself. Understanding these techniques may also help you read and understand proofs written by other people. Unfortunately, the techniques in this text do not give a step-by-step procedure for solving every proof problem. When trying to write a proof you may make a few false starts before finding the right way to proceed, and some proofs may require some cleverness or insight.
Mathematicians usually state the answer to a mathematical question in the form of a theorem that says that if certain assumptions called the hypotheses of the theorem are true, then some conclusion must also be true. Often the hypotheses and conclusion contain free variables, and in this case it is understood that these variables can stand for any elements of the universe of discourse. An assignment of particular values to these variables is called an instance of the theorem, and in order for the theorem to be correct it must be the case that for every instance of the theorem that makes the hypotheses come out true, the conclusion is also true. If there is even one instance in which the hypotheses are true but the conclusion is false, then the theorem is incorrect. Such an instance is called a counterexample to the theorem.
If you find a counterexample to a theorem, then you can be sure that the theorem is incorrect, but the only way to know for sure that a theorem is correct is to prove it. A proof of a theorem is simply a deductive argument whose premises are the hypotheses of the theorem and whose conclusion is the conclusion of the theorem. Of course the argument should be valid, so we can be sure that if the hypotheses of the theorem are true, then the conclusion must be true as well.
17
Tasks for the text Proof Strategies Adapted from Křepinská, Housková, Bubeníkova: Rozšiřující materiály pro výuku anglického jazyka, Matfyzpress 2006.
1) Try to define there terms.
counterexample
guesswork
step-by-step procedure
discourse
deduction x induction
premises
valid
trial and error
2) Translate these words into Czech (Slovak)
Assumption..................................................
Hypotheses...................................................
Theorem.......................................................
Variable........................................................
Instance ........................................................
Conjecture...................................................
3) Answer these questions.
a) Why does the writer think that mathematicians are sceptical people? Do you agree?
b) How are jigsaw puzzles similar to proofs?
c) Why is understanding proof-writing techniques useful?
d) What is the necessary condition for a theorem to be correct?
e) What is a proof of a theorem?