Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Наименьший пример, опровергающий утверждение
Smallest example which falsifies a claim
В математике минимальный контрпример — это наименьший пример, опровергающий утверждение, а доказательство с помощью минимального контрпримера — это метод доказательства, сочетающий использование минимального контрпримера с идеями доказательства индукцией и доказательства от противного. Более конкретно, при попытке доказать утверждение P, сначала предполагается от противного, что оно ложно, и, следовательно, должен существовать хотя бы один контрпример. Относительно некоторого представления о размере (которое, возможно, потребуется тщательно выбрать), делается вывод о существовании контрпримера C, который является минимальным. В контексте аргументации, C обычно является чем-то гипотетическим (поскольку истинность P исключает возможность существования C), но можно утверждать, что если бы C существовал, то он обладал бы определёнными свойствами, которые, после применения рассуждений, аналогичных тем, что используются в индуктивном доказательстве, привели бы к противоречию, тем самым демонстрируя истинность утверждения P. Если форма противоречия заключается в том, что можно получить другой контрпример D, меньший, чем C, в смысле рабочей гипотезы о минимальности, то эта техника традиционно называется доказательством бесконечного спуска. В этом случае может существовать несколько более сложных способов структурирования аргумента доказательства. Предположение о том, что если существует контрпример, то существует и минимальный контрпример, основано на некотором типе полного порядка. Обычный порядок натуральных чисел очевидно возможен, в соответствии с наиболее распространённой формулировкой математической индукции; однако область применения метода может включать в себя хорошо упорядоченную индукцию любого вида.
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. 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. 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.
Примеры
Метод минимального контрпримера широко использовался в классификации конечных простых групп. Теорема Фейта — Томпсона, утверждающая, что конечные простые группы, не являющиеся циклическими, имеют чётный порядок, была основана на предположении о существовании некоторой, а значит и минимальной, простой группы G нечётного порядка. Каждую собственную подгруппу G можно считать разрешимой, что позволяет применять обширную теорию таких подгрупп. Доказательство Евклида основной теоремы арифметики — это простой пример использования минимального контрпримера. Курант и Роббинс использовали термин «минимальный преступник» для обозначения минимального контрпримера в контексте теоремы о четырёх красках.
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 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. Courant and Robbins used the term minimal criminal for a minimal counter example in the context of the four color theorem.