mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

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

proof by 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), ... all hold. Infor ...

and

proof by contradiction In logic and mathematics, 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. Proof by contradiction is also known as ...

. 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 "John Smith is not a lazy student" is a ...

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

. 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 ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-o ...

of some kind. The usual ordering on the

natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...

s is clearly possible, by the most usual formulation of

mathematical induction Mathematical induction is a method for 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), ... all hold. Informal metaphors help ...

; but the scope of the method can include

well-ordered induction Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC. Induction by cases Let P(\alpha) be a property defined for a ...

of any kind.

Examples

The minimal counterexample method has been much used in the

classification of finite simple groups In mathematics, the classification of the finite simple groups is a result of group theory stating that every finite simple group is either cyclic, or alternating, or it belongs to a broad infinite class called the groups of Lie type, or else it ...

. The

Feit–Thompson theorem In mathematics, the Feit–Thompson theorem, or odd order theorem, states that every finite group of odd order is solvable. It was proved by . History conjectured that every nonabelian finite simple group has even order. suggested using th ...

, that finite simple groups that are not

cyclic group In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...

s 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 In mathematics, more specifically in the field of group theory, a solvable group or soluble group is a group that can be constructed from abelian groups using extensions. Equivalently, a solvable group is a group whose derived series terminates ...

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

References

{{Reflist Mathematical proofs Mathematical terminology