I am taking a basic analysis course. This is a general question that I often encounter in weekly homework. How should we start to attack this type of question: if the statement is true, prove it; if not true, give a counterexample? Yesterday evening I spent four hours looking for a counterexample, and finally figured that the statement was indeed true. I tried so hard to find a counterexample because I was not able to prove the statement at first. Are there any steps to follow in terms of this type of questions? In particular, sometimes a statement does not look like it is true. In this case, how can I quickly figure out whether I should try counterexamples or keep the efforts on proving the statement is true? The core problem is that this type of question is very time-consuming according to my homework experience. I desperately doubt I could figure out a correct answer during a timed exam next week.
Proof Writing – How to Attack ‘If True, Prove It; If Not True, Give a Counterexample’ Question
problem solvingproof-writingsoft-question
Related Solutions
Kempe's "proof" used induction on the number of vertices in the graph G. Given a graph with n vertices, he removed a vertex, colored the remaining graph in four colors using the inductive hypothesis, and then (and this is the hard part) re-inserted the missing vertex, which possibly resulted in having to "fix up" the coloring of its adjacent vertices - this is where the problem occurred.
The Heawood counterexample showed very clearly why the algorithm that Kempe used was invalid - when applied to Heawood's graph, it did not have the intended result. Thus it was this algorithmic portion of the proof that had a logical error that was exposed by the Heawood counterexample.
There are quite a few expositions of this entire affair; one chosen more or less at random is at http://web.stonehill.edu/compsci/LC/Four-Color/Four-color.htm
Has anyone tried as an additional technique the "fill-in" method?
This is based on the tried and tested method of teaching called "reverse chaining". To illustrate it, if you are teaching a child to put on a vest, you do not throw it the vest and say put it on. Instead, you put it almost on, and ask the child to do the last bit, and so succeed. You gradually put the vest less and less on, the child always succeeds, and finally can put it on without help. This is called error-less learning and is a tried and tested method, particularly in animal training (almost the only method! ask any psychologist, as I learned it from one).
So we have tried writing out a proof that, say, the limit of the product is the product of the limits, (not possible for a student to do from scratch), then blanking out various bits, which the students have to fill in, using the clues from the other bits not blanked out. This is quite realistic, where a professional writes out a proof and then looks for the mistakes and gaps! The important point is that you are giving students the structure of the proof, so that is also teaching something.
This kind of exercise is also nice and easy to mark!
Finally re failure: the secret of success is the successful management of failure! That can be taught by moving slowly from small failures to extended ones. This is a standard teaching method.
Additional points: My psychologist friend and colleague assured me that the accepted principle is that people (and animals) learn from success. This is also partly a question of communication.
Another way of getting this success is to add so many props to a situation that success is assured, and then gradually to remove the props. There are of course severe problems in doing all this in large classes. This will require lots of ingenuity from all you talented young people! You can find some more discussion of issues in the article discussing the notion of context versus content.
My own bafflement in teenage education was not of course in mathematics, but was in art: I had no idea of the basics of drawing and sketching. What was I supposed to be doing? So I am a believer in the interest and importance of the notion of methodology in whatever one is doing, or trying to do, and here is link to a discussion of the methodology of mathematics.
Dec 10, 2014 I'd make another point, which is one needs observation, which should be compared to a piano tutor listening to the tutees performance. I have tried teaching groups of say 5 or 6, where I would write nothing on the board, but I would ask a student to go to the board, and do one of the set exercises. "I don't know how to do it!" "Well, why not write the question on the board as a start." Then we would proceed, giving hints as to strategy, which observation had just shown was not there, but with the student doing all the writing.
In an analysis course, when we have at one stage to prove $A \subseteq B$, I would ask the class: "What is the first line of the proof?" Then: "What is the last line of the proof?" and after help and a few repetitions they would get the idea. I'm afraid grammar has gone out of the school syllabus, as "old fashioned"!
Seeing maths worked out in real time, with failures, and how a professional deals with failure, is essential for learning, and at the reasearch level. I remember thinking after an all day session with Michael Barratt in 1959: "Well, if Michael Barratt can try one damn fool thing after another, then so can I!", and I have followed this method ever since. (Mind you his tries were not all that "damn fool", but I am sure you get the idea.) The secret of success is the successful management of failure, and this is perhaps best learned from observation of how a professional deals with failure.
Best Answer
I disagree with the approach of proving by contradiction as a start.
In most cases, and which ones are the exception simply requires experience, you should just start by trying to prove the statement as if it were true. There's no point in starting with a proof by contradiction. Just try to prove it.1
If you are careful, and again experience is needed here, then your derivation will either be successful, or you will get stuck.
Now ask yourself. Why did you get stuck? Maybe you need to assume that $x+1=y$, or maybe you need to assume that the function is continuous at $0$. Who knows? It depends on the problem and on your attempt to prove it. The next step, then, is to try and engineer a counterexample using the failure of this assumption. If you need to assume $x+1=y$ in order for it to work, take an example where $x=0$ and $y=3$. And so on. If that works, well done, you found a counterexample, and you even got a free bonus information: you found a condition that will let you complete the proof.
Of course, it might be that your attempt at a proof was bad. Maybe you tried to do something wrong. Who knows. But if your attempted counterexample failed, that gives you new information, it tells you that the information you thought was crucial for the proof is in fact not crucial for the proof.
So you have to start over again, and try a different method and a different approach. And repeat this until the result is satisfactory.
Unfortunately, it will not be the case that this will always work. Sometimes you are missing a crucial piece of knowledge that would simplify the work. Or sometimes you just made a series of mistakes in your proof, and you thought you proved it, whereas you haven't actually proved the right statement. This is why it is a good idea to work with a friend, where you can check each other and discuss these kind of things.
One last thing, which might be worth discussing, is how to approach a proof to begin with. Well, if you want to prove that things fall down to the earth, you start by letting a few things fall down and see how that works out. Similarly in mathematics, experimenting is not a bad idea. If you need to prove some equation holds, try plugging in some small numbers, $0$ and $1$ are perhaps $\sqrt2$, if the equation makes it convenient. If you have to prove something about functions, try a constant function, or $e^x$, or whatever.
Toy examples are very important towards understanding why something is true, and if you get some general idea as to why something might be true, it will also give you an idea as to how it should be proved.