mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, a minimal counterexample is the smallest example which falsifies a claim, and a proof by minimal counterexample is a method of

proof Proof most often refers to: * Proof (truth), argument or sufficient evidence for the truth of a proposition * Alcohol proof, a measure of an alcoholic drink's strength Proof may also refer to: Mathematics and formal logic * Formal proof, a co ...

which combines the use of a minimal counterexample with the methods of proof by induction and

proof by contradiction In logic, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition by showing that assuming the proposition to be false leads to a contradiction. Although it is quite freely used in mathematical pr ...

. More specifically, in trying to prove a proposition ''P'', one first assumes by contradiction that it is false, and that therefore there must be at least one

counterexample A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "student John Smith is not lazy" is a c ...

. With respect to some idea of size (which may need to be chosen carefully), one then concludes that there is such a counterexample ''C'' that is ''minimal''. In regard to the argument, ''C'' is generally something quite hypothetical (since the truth of ''P'' excludes the possibility of ''C''), but it may be possible to argue that if ''C'' existed, then it would have some definite properties which, after applying some reasoning similar to that in an inductive proof, would lead to a contradiction, thereby showing that the proposition ''P'' is indeed true. If the form of the contradiction is that we can derive a further counterexample ''D'', that is smaller than ''C'' in the sense of the working hypothesis of minimality, then this technique is traditionally called

proof by infinite descent In mathematics, a proof by infinite descent, also known as Fermat's method of descent, is a particular kind of proof by contradiction used to show that a statement cannot possibly hold for any number, by showing that if the statement were to hold f ...

. In which case, there may be multiple and more complex ways to structure the argument of the proof. The assumption that if there is a counterexample, there is a minimal counterexample, is based on a

well-ordering In mathematics, a well-order (or well-ordering or well-order relation) on a set is a total ordering on with the property that every non-empty subset of has a least element in this ordering. The set together with the ordering is then called ...

of some kind. The usual ordering on the

natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...

s is clearly possible, by the most usual formulation of

mathematical induction Mathematical induction is a method for mathematical proof, proving that a statement P(n) is true for every natural number n, that is, that the infinitely many cases P(0), P(1), P(2), P(3), \dots all hold. This is done by first proving a ...

; but the scope of the method can include well-ordered induction of any kind.

Examples

The minimal counterexample method has been much used in the

classification of finite simple groups In mathematics, the classification of finite simple groups (popularly called the enormous theorem) is a result of group theory stating that every List of finite simple groups, finite simple group is either cyclic group, cyclic, or alternating gro ...

. The Feit–Thompson theorem, that finite simple groups that are not cyclic groups have even order, was proved 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. Euclid's proof of the fundamental theorem of arithmetic is a simple proof which uses a minimal counterexample. Courant and Robbins used the term minimal criminal for a minimal counterexample in the context of the

four color theorem In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions shar ...

. Here: p.495: ''"Since there is no point in making bad maps bigger, we go the opposite way and look at the smallest bad maps, colloquially known as minimal criminals."''

References

{{Reflist Mathematical proofs Mathematical terminology