Why does one counterexample disprove a conjecture?

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.