Minimal counterexample

Minimal counterexample

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Structural induction — is a proof method that is used in mathematical logic (e.g., the proof of Łoś theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction. Structural recursion is a recursion… …   Wikipedia

  • Four color theorem — Example of a four colored map A four colori …   Wikipedia

  • Cycle double cover — Unsolved problems in mathematics Does every bridgeless graph have a multiset of cycles covering every edge exactly twice? …   Wikipedia

  • Emmy Noether — Amalie Emmy Noether Born 23 March 1882(1882 03 23) …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • 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 Walter Feit and John Griggs Thompson (1962, 1963) Contents 1 History 2 Significance of the proof …   Wikipedia

  • Fundamental theorem of arithmetic — In number theory, the fundamental theorem of arithmetic (or unique prime factorization theorem) states that every natural number greater than 1 can be written as a unique product of prime numbers. For instance, : 6936 = 2^3 imes 3 imes 17^2 , ,! …   Wikipedia

  • 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… …   Wikipedia

  • Conway's thrackle conjecture — A thrackle is an embedding (in the plane) of a graph, such that each edge is a Jordan arc and every pair of edges meet once. Edges may either meet at a common endpoint, or, if they have no endpoints in common, at a point in their interiors. In… …   Wikipedia

  • Per Enflo — Born 1944 Stockholm, Sweden …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”