Minimal counterexample

In mathematics, the method of considering a minimal counterexample combines the ideas of inductive proof and proof by contradiction.^[1] Abstractly, in trying to prove a proposition P, one assumes that it is false, and that therefore there is at least one counterexample. With respect to some idea of size, which may need to be chosen skillfully, one assumes that there is such a counterexample C that is minimal. We expect that C is something quite hypothetical (since we are trying to prove P), but it may be possible to argue that if C existed, it would have some definite properties. From those we then try to get a contradiction.

If the form of the contradiction is that we can derive a further counterexample D, and that D is smaller than C in the sense of the working hypothesis of minimality, then this technique is traditionally called infinite descent. There may however be more complicated ways to argue. For example, the minimal counterexample method has been much used in the classification of finite simple groups. The Feit–Thompson theorem, that finite simple groups that are not cyclic groups have even order, was based on the hypothesis of some, and therefore some minimal, simple group G of odd order. Every proper subgroup of G can be assumed a solvable group, meaning that much theory of such subgroups could be applied.

The assumption that if there is a counterexample, there is a minimal counterexample, is based on a well-ordering of some kind. The usual ordering on the natural numbers is clearly possible, by the most usual formulation of mathematical induction; but the scope of the method is well-ordered induction of any kind.

Euclid's proof of the fundamental theorem of arithmetic is a simple proof using a minimal counterexample.

References