# Why does one counterexample disprove a conjecture?

Can't a conjecture be correct about most solutions except maybe a family of solutions? For example, a few centuries ago it was widely believed that $2^{2^n}+1$ is a prime number for any $n$ . For $n=0$ we get $3$ , for $n=1$ we get $5$ , for $n=2$ we get $17$ , for $n=3$ we get $257$ , but for $n=4$ it was too difficult to find if this was a prime, until Euler was able to find a factor of it. It seems like this conjecture stopped after that. But what if this conjecture isn't true only when $n$ satisfies a certain equation, or when $n$ is a power of $2$ $\ge$ $4$ , or something like that? Did anybody bother to check? I am not asking about this conjecture specifically, but as to why we consider one counterexample as proof that a conjecture is totally wrong.

P.S. Andre Nicolas pointed out that Euler found a factor when $n=5$, not $4$ .

-
You are right, it did not stop. There has been work on the type of $n$ for which $F_n$ must be non-prime. And there was considerable work developing specialized algorithms for testing primality of Fermat numbers, And much more. Work on Fermat numbers has never ceased. By the way, it is $F_5$ that Euler proved non-prime. –  André Nicolas Jul 10 '13 at 22:44
The conjecture that it was true for all $n$ stopped there, but we still ask question about whether it is true for infinitely many $n$, whether it is true for any more $n$, whether it is false for only finitely many $n$. The original conjecture ended, but there are all sorts of other questions, none of which have yet been answereed. That's not because nobody cares, it's because nobody has been able to answer them. –  Thomas Andrews Jul 10 '13 at 22:52
It would be historically not quite right to think that in the late $17$-th century and early $18$-th, it was widely believed that the Fermat numbers were prime. In fact, Fermat's assertion had been essentially forgotten. –  André Nicolas Jul 10 '13 at 23:34
Am i missing something, or just REALLY bad at math...but isn't 2^2^0 = 2? Which means that n=0 yields 3, not 1? –  acolyte Jul 11 '13 at 15:17
@acolyte you are correct. $2^{2^0} = 2 \implies 2^{2^0}+1 = 3$. –  apnorton Jul 11 '13 at 15:36

This is because, in general, a conjecture is typically worded "Such-and-such is true for all values of [some variable]." So, a single counter-example disproves the "for all" part of a conjecture.

However, if someone refined the conjecture to "Such-and-such is true for all values of [some variable] except those of the form [something]." Then, this revised conjecture must be examined again and then can be shown true or false (or undecidable--I think).

For many problems, finding one counter-example makes the conjecture not interesting anymore; for others, it is worthwhile to check the revised conjecture. It just depends on the problem.

-
Can you give an example of a problem where one counter example makes the conjecture uninteresting? I can't think of any, except where it's easy to generalize the counter example to a vast class of counter examples. –  Jack M Jul 11 '13 at 0:54
@JackM Those sorts of counter-examples are the ones I'm referring to. To make something up, a simple "conjecture" is that "every odd number greater than one is prime." The first counter-example is $9$, but just that is enough to make the conjecture uninteresting. :) (A silly example, for sure, but it illustrates my point.) –  apnorton Jul 11 '13 at 1:07
@anorton Not silly at all, that was the example I just wanted to suggest as well. Then again, your "conjecture" might inspire the conjecture "all primes but the number 2 are odd" –  Tobias Kienzler Jul 11 '13 at 8:29

A statement that

every $x$ with property $P$ also has property $Q$

is clearly disproved if one finds an object with property $P$ but not property $Q$. It takes only one such example to prove that the every is incorrect. If the conjecture were that

all but at most finitely many $x$ with property $P$ have property $Q$,

then of course one counterexample would not refute the conjecture: one would need to produce infinitely many counterexamples. But that would be a different conjecture.

-
This raises an important point which is that all theorems are implications. They may not have to be expressed as implications, but they are. This is even more obvious when you look at proof theory. A claim "for all x, P(x) entails Q(x)" is disproven by finding an x such that P(x) is valid and Q(x) is false. However, in the real world, it's possible that a conjecture is "almost" true, in the sense that P(x) needs some more conditions. It's well known that some proofs of Euclid are "almost" true, in that there are some nondegeneracy conditions which Euclid didn't consider. –  Pseudonym Jul 11 '13 at 2:16

Conjectures are usually proposed about some set of objects belonging to some set or domain, objects which are clearly identified. Let's call this domain $D$.

The conjecture about $x \in D$ includes some property $P(x)$ that is claimed to hold for all $x$ in the Domain D.

So at its simplest, interesting conjectures are of the form

$$\forall x (x \in D \implies P(x)\tag{\dagger}$$

Then we let the refutation begin! A conjecture $(\dagger)$ is proposed, and mathematicians begin the fun work of attempting to prove or disprove it.

All it takes to successfully refute $\dagger$ is to find a counterexample: an $x \in D$ such that $P(x)$ fails to hold. The negation of a universally qualified statement like $(\dagger)$ is a statement of the form:

$$\exists x(x\in D \land \lnot P(x))$$

That's it.

What happens then depends on the significance of the conjecture:

Given a conjecture that (many) mathematicians find fascinating, work rarely stops when one counterexample disproves a conjecture that some property holds for all $x$ meeting some criteria. The criteria may simply be refined, by revising $P(x)$ or by introducing additional restrictions on the domain.

Then more effort is made to test the refined conjecture's veracity.

This process often continues until enough qualifications and exceptions are introduced to the extent that the conjecture becomes too uninteresting to modify further.

The process never ends, though. When one problem becomes uninteresting, then mathematicians propose, or wait to pounce upon, other interesting conjectures.

-
$_{+1}^{+1}{_{+1}^{+1}}\Large{+1}_{{+1}^{+1}_{{+1}^{+1}}}$ –  Babak S. Jul 11 '13 at 7:19
Wow, @Babak That's artistry! –  amWhy Jul 11 '13 at 15:18
@amWhy: Nice write up +1 –  Amzoti Jul 12 '13 at 1:14

A mathematical statement is either true or false (well, provability theory aside, since that's not the issue here). If you make a specific conjecture $C=\forall x: P(x)$, and you find a specific counterexample $x'$ with $\neg P(x')$, then you have disproved $C$.

If you specify a family of conjectures $C(\mu)$ and find a counterexample $x'_\mu$ for one particular $\mu$ then obviously you haven't said anything about all the other conjectures. But people rarely formulate such large classes of conjectures.

You might however make weakened conjectures, like $\tilde C=\{x:\neg P(x)\} \text{ is a finite set}$, the statement that there are only finitely many counterexamples. This is, however, a completely different conjecture.

A key point is that often the proof techniques and applications of the result would be very different for e.g. $C$ and $\tilde C$, so whether you believe one or the other makes a very important difference. In some situations, one counterexample ruins everything, in other situations, you couldn't care less if there were only an in some sense "small" set of exceptions.

-

A conjecture often of the form $\forall x P(x)$; the negation of this is $\exists x {\sim}P(x)$. The negation of a universal statement is existential; to negate a universal statement one must just find a counterexample.

-