{{short description|Smallest example which falsifies a claim}} {{redirect|Minimal criminal|the musical project|Minimal Criminal (project)}} In [[mathematics]], a '''minimal counterexample''' is the smallest example which falsifies a claim. It is also sometimes called a '''minimal criminal''',<ref>{{Cite book |last=belcastro |first=sarah-marie |url=https://www.google.com.br/books/edition/Discrete_Mathematics_with_Ducks/UYtlK8waqasC |title=Discrete Mathematics with Ducks |date=2012-06-21 |publisher=CRC Press |isbn=978-1-4665-0499-8 |pages=107 |language=en}}</ref> '''smallest criminal''',<ref>{{Cite book |last=Hofmann |first=Karl H. |url=https://www.google.com.br/books/edition/The_Structure_of_Compact_Groups/tlw8EAAAQBAJ |title=The Structure of Compact Groups: A Primer for the Student – A Handbook for the Expert |last2=Morris |first2=Sidney A. |date=2020-06-08 |publisher=Walter de Gruyter GmbH & Co KG |isbn=978-3-11-069601-1 |pages=250 |language=en}}</ref> or '''least criminal''',<ref>{{Cite book |url=https://www.google.com.br/books/edition/Mathematics_Magazine/CNE3AAAAIAAJ |title=Mathematics Magazine |date=1981 |publisher=Mathematical Association of America |volume=54 |pages=24 |language=en}}</ref><ref>{{Cite book |last=Cameron |first=Peter Jephson |url=https://www.google.com.br/books/edition/Introduction_to_Algebra/syYYl-NVM5IC |title=Introduction to Algebra |date=1998 |publisher=Oxford University Press |isbn=978-0-19-850195-4 |pages=17 |language=en}}</ref> especially (but not exclusively) in the context of the [[Four color theorem|four-color theorem]].<ref name=":0">{{Cite book |last=Wilson |first=Robin |author-link=Robin Wilson (mathematician) |url=https://www.google.com.br/books/edition/Four_Colors_Suffice/1Q48EAAAQBAJ |title=Four Colors Suffice: How the Map Problem Was Solved - Revised Color Edition |date=2021-10-12 |publisher=Princeton University Press |isbn=978-0-691-23756-5 |pages=51-52 |language=en}}</ref><ref name=":1">{{Cite book |last=Fritsch |first=Rudolf |url=https://www.google.com.br/books/edition/The_Four_Color_Theorem/me3jBwAAQBAJ |title=The Four-Color Theorem: History, Topological Foundations, and Idea of Proof |last2=Fritsch |first2=Gerda |date=2012-12-06 |publisher=Springer Science & Business Media |isbn=978-1-4612-1720-6 |pages=85-87 |language=en}}</ref><ref name=":2">{{Cite book |last=Wilson |first=Robert |url=https://www.google.com.br/books/edition/Graphs_Colourings_and_the_Four_colour_Th/9FPCJUCc7QEC |title=Graphs, Colourings and the Four-colour Theorem |date=2002 |publisher=Oxford University Press |isbn=978-0-19-851061-1 |pages=36 |language=en}}</ref><ref name=":3">{{Cite book |last=Xu |first=Jin |url=https://www.google.com.br/books/edition/Maximal_Planar_Graph_Theory_and_the_Four/RalfEQAAQBAJ |title=Maximal Planar Graph Theory and the Four-Color Conjecture |date=2025-05-23 |publisher=Springer Nature |isbn=978-981-96-4745-3 |pages=95 |language=en}}</ref><ref name=":4">{{cite book |author1=Richard Courant |author1-link=Richard Courant |url= |title=What is Mathematics? |author2=Herbert Robbins |author2-link=Herbert Robbins |publisher=Oxford University Press |year=1996 |isbn=9780195105193 |edition=2nd |location=Oxford}} 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."''</ref> A '''proof by minimal counterexample''' (or by ''minimal/smallest/least criminal'') is a method of [[mathematical proof|proof]] which combines the use of a minimal counterexample with the methods of [[Proof By Induction|proof by induction]] and [[proof by contradiction]].<ref>[[Gary Chartrand|Chartrand, Gary]], Albert D. Polimeni, and [[Ping Zhang (graph theorist)|Ping Zhang]]. Mathematical Proofs: A Transition to Advanced Mathematics. Boston: Pearson Education, 2013. Print.</ref><ref>{{Cite web|url=http://alpha.math.uga.edu/~mklipper/3200/F12/mincounter.pdf|title=Proof by Minimum Counterexample|last=Klipper|first=Michael|date=Fall 2012|website=alpha.math.uga.edu|url-status=dead|archive-url=https://web.archive.org/web/20180417050633/http://alpha.math.uga.edu/~mklipper/3200/F12/mincounter.pdf|archive-date=2018-04-17|access-date=2019-11-28}}</ref> 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.<ref>{{Cite web|url=http://math.furman.edu/~tlewis/math260/scheinerman/chap4/sec20.pdf|title=§20 Smallest Counterexample|last=Lewis|first=Tom|date=Fall 2010|website=math.furman.edu|archive-url=|archive-date=|access-date=2019-11-28}}</ref>
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 number]]s 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 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.<ref>{{Citation | last1=Feit | first1=Walter | author1-link=Walter Feit | last2=Thompson | first2=John G. | author2-link=John G. Thompson | title=Solvability of groups of odd order | url=http://projecteuclid.org/Dienst/UI/1.0/Journal?authority=euclid.pjm&issue=1103053941 | mr=0166261 | year=1963 | journal=Pacific Journal of Mathematics | issn=0030-8730 | volume=13 | pages=775–1029| doi=10.2140/pjm.1963.13.775 | doi-access=free }}</ref>
[[Fundamental theorem of arithmetic#Proof|Euclid's proof of the fundamental theorem of arithmetic]] is a simple proof which uses a minimal counterexample.<ref>{{Cite web|url=https://undergroundmathematics.org/divisibility-and-induction/the-fundamental-theorem-of-arithmetic|title=The Fundamental Theorem of Arithmetic {{!}} Divisibility & Induction {{!}} Underground Mathematics|website=undergroundmathematics.org|access-date=2019-11-28}}</ref><ref>{{Cite web|url=https://www.dpmms.cam.ac.uk/~wtg10/FTA.html|title=The fundamental theorem of arithmetic|website=www.dpmms.cam.ac.uk|access-date=2019-11-28}}</ref>
A minimal counterexample has often been used in proofs of the [[Four color theorem|four-color theorem]], where it is usually called a ''minimal criminal''.<ref name=":0" /><ref name=":1" /><ref name=":2" /><ref name=":3" /><ref name=":4" />
== References == {{Reflist}}
[[Category:Mathematical proofs]] [[Category:Mathematical terminology]]