Минимальный контрпример

В математике минимальный контрпример - это наименьший пример, опровергающий утверждение, а доказательство с помощью минимального контрпримера - это метод доказательства, который сочетает в себе использование минимального контрпримера с идеями доказательства по индукции и доказательства от противного. Точнее. пытаясь доказать предложение P, сначала предполагается от противного, что оно ложно и, следовательно, должен существовать по крайней мере один контрпример. Что касается некоторого представления о размере (которое, возможно, потребуется тщательно выбирать), можно сделать вывод, что существует такой контрпример C, который является минимальным. Что касается аргументации, C обычно является чем-то довольно гипотетическим (поскольку истинность P исключает возможность C), но можно утверждать, что если бы C существовал, то у него были бы некоторые определенные свойства, которые после применения некоторых рассуждений аналогично индуктивному доказательству, привело бы к противоречию, тем самым показывая, что утверждение P действительно верно.

Если форма противоречия такова, что мы можем вывести дополнительный контрпример D, который меньше, чем C в смысле рабочей гипотезы минимальности, то эту технику традиционно называют доказательством бесконечного спуска. В этом случае может быть несколько и более сложных способов структурировать аргументы доказательства.

Предположение, что если есть контрпример, есть минимальный контрпример, основано на хорошо упорядоченном некоторого вида. Обычное упорядочивание натуральных чисел очевидно возможно, с помощью наиболее обычной формулировки математической индукции ; но область применения метода может включать упорядоченную индукцию любого вида.

Метод минимального контрпримера широко использовался при классификации конечных простых групп. Теорема Фейта – Томпсона о том, что конечные простые группы, не являющиеся циклическими группами, имеют четный порядок, была основана на предположении о некоторой и, следовательно, некоторой минимальной простой группе G нечетного порядка. Каждую собственную подгруппу группы G можно считать разрешимой группой, что означает, что большая часть теории таких подгрупп может быть применена.

Евклид доказал основную теорему арифметики - это простое доказательство, использующее минимальный контрпример.