Proof By Counterexample

Artificial intelligence programs have recent disproved some famous mathematical conjectures by finding counter-examples.

Most mathematical proofs are deductive. They reason, point by point, from axiom, to lemma, to theorem, in a straight forward, X implies Y, Y implies Z, fashion.

Some mathematical proofs, arguably more elegant ones, are inductive. A common structure of an inductive proof is roughly speaking: imagine that this theorem is not true. Then, X could imply Y, and if X implies Y, then Z must have a certain value, but Z can have a different value. Therefore, the theorem must be true.

Another form of inductive proof shows that if proposition X is true that proposition X+1 is true by deduction. Then, it shows that proposition X is true in a separate proof for a particular early case of X (and possibly by other separate proofs for several other early cases of X that come before the one you use to validate the rest of the cases). Thus, for the early case or cases, and all subsequent cases, the conjecture must be true.

Many theorems are also almost always true, but have some "trivial" exceptions, typically for things like values of variables that are equal to zero or one, or for the first few iterations of a series, with the theorem holding only after those iterations.

One of the most elegant and efficient ways to prove that a theorem is not true is with a counterexample. The theorem may be true for every situation or set of values considered, sometimes millions of them, but it takes only one counterexample to show that the theorem is not always true, and hence, is false.

For example, in the case of Fermat's Last Theorem, before it was prove to be true, one could have imagined a counterexample disproving it with just three whole numbers that defied it's rule, that could be stated in a line or two, even thought it has been numerically tested for millions of numbers and in the end, it it would take a proof hundreds of pages long to rigorously establish that it was true deductively.

Disproof of longstanding mathematical conjectures by counterexample is rare, but it has happened, even in the pre-computer era, for theorems that held in vast numbers of examples, with no flaws identified for many decades by extremely smart people trying hard to do so.

I haven't very exactly described this kind of conjecture, although I'm sure that a clever mathematician could do so, but let's assume for sake of argument that this kind of conjecture is susceptible to precise definition, and call this kind of conjecture a "near miss conjecture". 

Disproof of a near miss conjecture by counterexample, however, in and of itself, while it is efficient, indeed elegant, is also dissatisfying in the case of conjectures the hold true for so many examples and which defied logical reasoning to show that they are true or false for long periods of active efforts to do so. Disproof of a near miss conjecture by counterexample is dissatisfying because, while they do show that the conjecture is not true, they don't tell why the conjecture doesn't always work, even though it does work for so many cases and logically feels like it should work in every case.

Maybe the near miss conjecture is true for all but a finite set of counterexamples that is well defined, and can be used to modify the conjecture in much the same way as many theorems are modified to exclude a handful of trivial exceptions.

Maybe the near miss conjecture could be true if some other assumption so obvious that even smart people don't recognize that it needs to be made, add it. 

For example, a conjecture about the probability of heads or tails in a coin toss may need to be supplemented with the assumption that the coin doesn't land on its side and thus doesn't generate either a heads or a tails result, rescuing the near miss conjecture, which remains very useful, despite not being perfectly true without the added assumption.

Knowing why a disproof by counterexample is possible adds insight that the counterexample itself often does not.