From Concrete Mathematics:
Incidentally, when we’re faced with a “prove or disprove,” we’re usually better off trying first to disprove with a counterexample, for two reasons: A disproof is potentially easier (we just need one counterexample); and nit-picking arouses our creative juices. Even if the given assertion is true, out search for a counterexample often leads us to a proof, as soon as we see why a counterexample is impossible. Besides, it’s healthy to be skeptical.
Depending on the question, it’s not always that disproving something is done just by showing a counterexample.
In computability theory, when you say that a problem can not be recognized/generated/accepted by a model, you must show that *all* machines fail computing it. In this case, proving is easier. One just need to show the device that recognizes it.
So the general principle is really something like: The first thing to try is to look for a concrete example that would settle the question. Sometimes that’s a proof, sometimes a disproof.
In reality, when you have a research problem where you don’t whether the answer is true or false, you work on both ends simultaneously. You start to construct a proof; at some point, you encounter an obstacle in your proof — for example, maybe your proof fails if the one set of parameters (call it parameter “A”) grows very large. You then think whether there is an example where the parameter A does get large. If so, either you figure out how to prove it in that case, or you have your counter-example.
But more likely, in case the parameter A gets large, you can still prove it as long as parameter B does not also get large. So a counterexample could now come from inventing an object where A and B are large simultaneously. And so on…
In my experience, it generally only works for constructive proofs, because a constructive proof is basically an algorithm for constructing a solution.
There are exceptions; I’ve come up with a few existence proofs by trying to disprove something. But generally speaking, non-constructive proofs require some clevereness that constructive proofs usually don’t.
Hi John,
You once asked me, long ago, if I had some problem I wanted help with. Now I have one. Can you or answer (prove or disprove) this statistically related problem: http://stats.stackexchange.com/questions/57725/is-the-square-root-of-the-symmetric-kullback-leibler-divergence-a-metric I have not yet been able to get an answer.
Tomas, it looks to me as if the answer is yes (see my answer on stats.stackexchange.com) but I am not an expert and haven’t scrutinized the paper that claims to prove the key result. Take a look.