Minimal counterexample
Encyclopedia
In mathematics
, the method of considering a minimal counterexample (or minimal criminal) combines the ideas of inductive proof and proof by contradiction. 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 infinite simple groups that are not cyclic group
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
, 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 number
s 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the method of considering a minimal counterexample (or minimal criminal) combines the ideas of inductive proof and proof by contradiction. Abstractly, in trying to prove a proposition P, one assumes that it is false, and that therefore there is at least one counterexample
Counterexample
In logic, and especially in its applications to mathematics and philosophy, a counterexample is an exception to a proposed general rule. For example, consider the proposition "all students are lazy"....
. 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
Infinite descent
In mathematics, a proof by infinite descent is a particular kind of proof by contradiction which relies on the fact that the natural numbers are well ordered. One typical application is to show that a given equation has no solutions. Assuming a solution exists, one shows that another exists, that...
. 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
Classification of finite simple groups
In mathematics, the classification of the finite simple groups is a theorem stating that every finite simple group belongs to one of four categories described below. These groups can be seen as the basic building blocks of all finite groups, in much the same way as the prime numbers are the basic...
. The Feit–Thompson theorem
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...
, that infinite simple groups that are not cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
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
Solvable group
In mathematics, more specifically in the field of group theory, a solvable group is a group that can be constructed from abelian groups using extensions...
, 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 number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s is clearly possible, by the most usual formulation of mathematical induction
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
; 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.