A proof is a connected series of statements intended to establish a proposition1. There are some tips on proving things below. But this page is about what is not a proof! Now, as you read these examples, you may find yourself thinking, “Well, those are obviously not valid proof techniques.” True. But in the heat of the moment during a frustrating problem, they can become very tempting.
Ways to not prove things:
- I tried very hard and failed to do this, therefore it can’t be done.
- This algorithm doesn’t work, therefore it can’t be done.
- I did a bunch of cases that didn’t work, therefore it can’t be done.
- It is obvious that this is impossible.
- I let n = 1, 2, 3, 4 and 5, and found a pattern. Therefore this pattern is true for all n.
- The theorem is true for the following example, therefore it is always true.
- Look at this picture.
- The hint said to show THIS first, so we can assume THIS is true.
- I am restating a definition, and therefore it is true.
(“7068555·2121301-1 is prime. Proof: 7068555·2121301-1 is only divisible by itself and 1”)
The curious thing is – these things are good steps on the way to constructing real proofs! To show something is impossible, you DO gain insight by trying to do it and seeing what goes wrong. To gain insight for a general n, you DO gain insight by letting n = 1, 2, 3, 4 and 5. To show a theorem is true, you DO gain insight by constructing an example. You DO gain insight by drawing lots of pictures. If you have a hint, you DO serve yourself well by taking it very seriously. And sometimes you DO find things easier to think about if you state them in a different way.
And many teachers (like me) WILL get excited and give you praise if they see you doing these things. And many teachers (like me) WILL do these things on the board. So I understand how you may start thinking that the techniques above are proofs. But they are not. I wish I could make them so.
Ways to actually prove things
The biggest advice I have to new proof writers: Feel free to introduce notation. If you find yourself constantly talking about “that first graph we talked about” and “the graph that we got from the first graph” you may want to start with “Let this graph be G, and obtain a new graph H by doing the following…” and then you can just call them G and H. You can name sets, functions, graphs, points, basis vectors, anything you want to.
Valid Techniques: Let’s prove that if it is raining, then Doug will get wet.
- You can prove things directly: Assume it is raining. Then step by step show that Doug will get wet.
- You can prove the contrapositive: You can equivalently assume that Doug is NOT wet, then step by step show it is NOT raining.
- You can prove by contradiction: Assume the statement is false. Explore the consequences, then find a contradiction. In our case, you would assume that it is raining, and Doug is dry, and demonstrate how this winds up destroying the laws of the universe.
There are other techniques, such as proof by induction, finding counter-examples, and all sorts of subject-specific techniques. But the above three will be your work-horses.
Tell us about the bar fight, John.