Prove or disprove

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.

6 thoughts on “Prove or disprove

  1. Alex Bredariol Grilo

    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.

  2. 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.

  3. 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…

  4. 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.

  5. 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.

Leave a Reply

Your email address will not be published. Required fields are marked *