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

В математике минимальный контрпример — это наименьший пример, опровергающий некоторое утверждение. Такой пример также иногда называют минимальным криминалом^[1], наименьшим криминалом^[2] или наименьшим нарушителем^[3][4], особенно (но не исключительно) в контексте теоремы о четырёх красках^{[5][6][7][8][9]}.

Доказательство методом минимального контрпримера (или методом минимального/наименьшего/наименьшего криминала) — это способ доказательства, сочетающий использование минимального контрпримера с методами доказательства по индукции и доказательство от противного^[10][11]. Более конкретно, при попытке доказать некоторое утверждение P сначала предполагается от противного, что оно ложно, и, следовательно, существует хотя бы один контрпример. С учётом некоторого понятия размера (которое может потребовать тщательного выбора) далее делается вывод, что существует такой контрпример C, который является минимальным. В рамках рассуждения C обычно является гипотетическим объектом (так как истинность P исключает существование C), однако можно показать, что если бы C существовал, то он обладал бы определёнными свойствами, которые, после применения рассуждений, аналогичных индуктивному доказательству, приводят к противоречию, тем самым доказывая истинность утверждения P^[12].

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

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