On the value of proofs vs counterexamples

369 Views Asked by At

If a conjecture doesn't hold we usually provide a counterexample. While re-proving theorems is valuable and mathematicians do it usually, I think proving that some statement is wrong without giving counterexample rather providing general argument to prove that it is wrong, should also be valuable. However, I have not seen such approaches. Why is that so?

Thank you.

4

There are 4 best solutions below

1
On BEST ANSWER

Let us examine a rather simple statement (which happens to be untrue):

If $n$ is an odd integer, then $n+n$ is likewise odd.

One can "disprove" this, by finding a particular $n$ as a counter-example: in this case $n = 1$ works nicely: $1 = 2\cdot 0 + 1$ is odd, but $1 + 1 = 2$ is even.

However, mathematicians often like to go "even further": and prove a stronger statement (which implies the weaker statement provided by our single counter-example):

If $n$ is an odd integer, $n+n$ is never odd.

A somewhat facile, but direct proof: $n+n = 2n$, which is even, and thus not odd.

A more typical approach:

Assume (by way of aiming to show a contradiction), that $n + n = 2k + 1$, for some integer $k$. Then $2(n-k) = 1$, for some integer $n-k$ (since the difference of two integers is an integer).

But clearly, $n - k = \dfrac{1}{2}$, which is not an integer, so we have a contradiction (Note this appeals to the rational numbers, which might be considered "unfair". If one wished to reason entirely within the integers, one would have to show that there is no integer $t$ with $2t = 1$. An outline of how one would do this: 1) show $t > 0$, 2) show $t < 1$, 3) conclude there is no such integer $t$).

A caveat: it may be that there is actually only one counter-example (something might be true for all natural numbers $n > 1$, but not for $1$ itself), that is, something is "almost true" (and can be turned into a true statement, with a minor modification). For example, there are a whole slew of mathematical statements involving "odd primes" (because $2$ is the only counter-example when considering a statement about all primes that is untrue for even primes).

3
On

My personal favorite: Do there exist irrationals, $a,b$ such that $a^b$ is rational? In terms of your question, the conjecture is that there do not exist $a,b$ such that $a^b$ is rational. This conjecture is false as shown below by contradiction:

Look at $(\sqrt{2})^{\sqrt{2}}$. If it's rational we're done. Otherwise it's irrational and $((\sqrt{2})^{\sqrt{2}})^{\sqrt{2}}=2$. So either $a=b=\sqrt{2}$ or $a=(\sqrt{2})^{\sqrt{2}}$,$b=\sqrt{2}$ give an answer. It's up to you to figure out which one is right!

7
On

Your statements are not true. If the conjecture is of the form "There exists a $T$ such that $P$", then to prove it you must prove that there is at least one $T$ such that $P$ holds (this may or may not be an explicit example), and to disprove it you do not give any counter-example whatsoever, but must rather prove that "For any $T$, $P$ does not hold.". Some examples:

  1. There exists a largest integer. False, and proven by showing that for any integer there is a larger one.
  2. There exists a continuous function on $\mathbb{R}$ that is not differentiable at any point. True, and proven by constructing such a function (two examples are the Weierstrass function and the Blancmange curve)
  3. There exists a monotonic function on $\mathbb{R}$ that is discontinuous at uncountably many points. False, and proven by showing that every such function is discontinuous only at countably many points.

But it is true that we like certain kinds of theorems. As user251257 said, many conjectures are of the form "For any ..., ...". This arises naturally because we want to be able to say as much as we can, so of course we would like to have universal quantification. But as you can see from the second example above, we also have some theorems that just assert the existence of a single object.

0
On

In many cases, having a specific counterexample can help you understand why a statement isn't true. I believe there's some evidence that inductive reasoning by synthesizing examples is a particularly natural way for most people to think, and thus an example or two can often contribute more to intuitive understanding of a problem than a fully general proof.

Given that counterexamples are desirable, the only cases where it really makes sense not to give a counterexample are those where it's infeasible to come up with one in the first place. I would imagine those cases are relatively uncommon.