Minimal counterexample

Last updated

In 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 and proof by contradiction. [1] [2] 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. 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. [3]

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 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 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 can include well-ordered induction of any kind.

Examples

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[ when? ] 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. [4] [5]

Courant and Robbins used the term minimal criminal for a minimal counter-example in the context of the four color theorem. [6]

Related Research Articles

<span class="mw-page-title-main">Conjecture</span> Proposition in mathematics that is unproven

In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis or Fermat's Last Theorem, have shaped much of mathematical history as new areas of mathematics are developed in order to prove them.

<span class="mw-page-title-main">Mathematical induction</span> Form of mathematical proof

Mathematical induction is a method for proving that a statement is true for every natural number , that is, that the infinitely many cases   all hold. Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:

Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung and that from each rung we can climb up to the next one.

Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics.

<span class="texhtml mvar" style="font-style:italic;">p</span>-group Group in which the order of every element is a power of p

In mathematics, specifically group theory, given a prime number p, a p-group is a group in which the order of every element is a power of p. That is, for each element g of a p-group G, there exists a nonnegative integer n such that the product of pn copies of g, and not fewer, is equal to the identity element. The orders of different elements may be different powers of p.

In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th-century Italian mathematician Giuseppe Peano. These axioms have been used nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of whether number theory is consistent and complete.

<span class="mw-page-title-main">Theorem</span> In mathematics, a statement that has been proved

In mathematics, a theorem is a statement that has been proved, or can be proved. The proof of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of the axioms and previously proved theorems.

In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which precedes if and only if is either or the sum of and some positive integer.

Structural induction is a proof method that is used in mathematical logic, computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction over natural numbers and can be further generalized to arbitrary Noetherian induction. Structural recursion is a recursion method bearing the same relationship to structural induction as ordinary recursion bears to ordinary mathematical induction.

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in contrast to the ordinary mathematical practice of deriving theorems from axioms. It can be conceptualized as sculpting out necessary conditions from sufficient ones.

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not vary smoothly in this way, but have distinct, separated values. Discrete mathematics, therefore, excludes topics in "continuous mathematics" such as calculus and analysis.

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 for a number, then the same would be true for a smaller number, leading to an infinite descent and ultimately a contradiction. It is a method which relies on the well-ordering principle, and is often used to show that a given equation, such as a Diophantine equation, has no solutions.

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.

<span class="mw-page-title-main">Burnside's theorem</span> Mathematic group theory

In mathematics, Burnside's theorem in group theory states that if G is a finite group of order where p and q are prime numbers, and a and b are non-negative integers, then G is solvable. Hence each non-Abelian finite simple group has order divisible by at least three distinct primes.

<span class="mw-page-title-main">Cauchy's theorem (group theory)</span> Existence of group elements of prime order

In mathematics, specifically group theory, Cauchy's theorem states that if G is a finite group and p is a prime number dividing the order of G, then G contains an element of order p. That is, there is x in G such that p is the smallest positive integer with xp = e, where e is the identity element of G. It is named after Augustin-Louis Cauchy, who discovered it in 1845.

In mathematics, a proof of impossibility is a proof that demonstrates that a particular problem cannot be solved as described in the claim, or that a particular set of problems cannot be solved in general. Such a case is also known as a negative proof, proof of an impossibility theorem, or negative result. Proofs of impossibility often are the resolutions to decades or centuries of work attempting to find a solution, eventually proving that there is no solution. Proving that something is impossible is usually much harder than the opposite task, as it is often necessary to develop a proof that works in general, rather than to just show a particular example. Impossibility theorems are usually expressible as negative existential propositions or universal propositions in logic.

Gentzen's consistency proof is a result of proof theory in mathematical logic, published by Gerhard Gentzen in 1936. It shows that the Peano axioms of first-order arithmetic do not contain a contradiction, as long as a certain other system used in the proof does not contain any contradictions either. This other system, today called "primitive recursive arithmetic with the additional principle of quantifier-free transfinite induction up to the ordinal ε0", is neither weaker nor stronger than the system of Peano axioms. Gentzen argued that it avoids the questionable modes of inference contained in Peano arithmetic and that its consistency is therefore less controversial.

A timeline of mathematical logic; see also history of logic.

In mathematics, the Ax–Grothendieck theorem is a result about injectivity and surjectivity of polynomials that was proved independently by James Ax and Alexander Grothendieck.

<span class="mw-page-title-main">Gopal Prasad</span> Indian-American mathematician

Gopal Prasad is an Indian-American mathematician. His research interests span the fields of Lie groups, their discrete subgroups, algebraic groups, arithmetic groups, geometry of locally symmetric spaces, and representation theory of reductive p-adic groups.

In Lie theory, an area of mathematics, the Kazhdan–Margulis theorem is a statement asserting that a discrete subgroup in semisimple Lie groups cannot be too dense in the group. More precisely, in any such Lie group there is a uniform neighbourhood of the identity element such that every lattice in the group has a conjugate whose intersection with this neighbourhood contains only the identity. This result was proven in the 1960s by David Kazhdan and Grigory Margulis.

References

  1. ↑ Chartrand, Gary, Albert D. Polimeni, and Ping Zhang. Mathematical Proofs: A Transition to Advanced Mathematics. Boston: Pearson Education, 2013. Print.
  2. ↑ Klipper, Michael (Fall 2012). "Proof by Minimum Counterexample" (PDF). alpha.math.uga.edu. Archived from the original (PDF) on 2018-04-17. Retrieved 2019-11-28.
  3. ↑ Lewis, Tom (Fall 2010). "§20 Smallest Counterexample" (PDF). math.furman.edu. Retrieved 2019-11-28.
  4. ↑ "The Fundamental Theorem of Arithmetic | Divisibility & Induction | Underground Mathematics". undergroundmathematics.org. Retrieved 2019-11-28.
  5. ↑ "The fundamental theorem of arithmetic". www.dpmms.cam.ac.uk. Retrieved 2019-11-28.
  6. ↑ Richard Courant; Herbert Robbins (1996). What is Mathematics? (2nd ed.). Oxford: Oxford University Press. ISBN   9780195105193. 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."
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.