Минимальный контрпример
В математике минимальный контрпример — это наименьший пример, который фальсифицирует утверждение, а доказательство с помощью минимального контрпримера — это метод доказательства, сочетающий использование минимального контрпримера с идеями доказательства по индукции и доказательства от противного . [1] [2] Точнее, пытаясь доказать предложение P , сначала предполагается от противного, что оно ложно и, следовательно, должен существовать хотя бы один контрпример . Что касается некоторой идеи размера (которая, возможно, должна быть выбрана тщательно), то можно прийти к выводу, что существует такой контрпример C , который является минимальным . Что касается аргумента, C вообще является чем-то совершенно гипотетичным (поскольку истинность P исключает возможность C ), но можно утверждать, что если бы C существовало, то оно имело бы некоторые определенные свойства, которые после применения некоторых рассуждений аналогично тому, как это происходит при индуктивном доказательстве, привело бы к противоречию, тем самым показав, что предложение P действительно истинно. [3]
Если форма противоречия такова, что мы можем вывести дополнительный контрпример D , меньший, чем C в смысле рабочей гипотезы минимальности, то этот метод традиционно называется доказательством путем бесконечного спуска . В этом случае может быть несколько и более сложных способов структурировать аргументацию доказательства.
Предположение о том, что если существует контрпример, то существует и минимальный контрпример, основано на хорошем упорядочении каком-то . Очевидно, что обычное упорядочение натуральных чисел возможно с помощью самой обычной формулировки математической индукции ; но область применения метода может включать в себя упорядоченную индукцию любую .
Примеры
[ редактировать ]Метод минимального контрпримера широко использовался при классификации конечных простых групп . Теорема Фейта –Томпсона о том, что конечные простые группы, не являющиеся циклическими группами , имеют четный порядок, была доказана на основе гипотезы о некоторой и, следовательно, некоторой минимальной простой группе G нечетного порядка. Каждую собственную подгруппу группы G можно считать разрешимой группой , а это означает, что к таким подгруппам можно применить большую часть теории. [4]
Доказательство Евклида основной теоремы арифметики — это простое доказательство, в котором используется минимальный контрпример. [5] [6]
Курант и Роббинс использовали термин «минимальный преступник» для обозначения минимального контрпримера в контексте теоремы о четырех цветах. [7]
Ссылки
[ редактировать ]- ^ Чартран, Гэри , Альберт Д. Полимени и Пин Чжан . Математические доказательства: переход к высшей математике. Бостон: Pearson Education, 2013. Печать.
- ^ Клиппер, Майкл (осень 2012 г.). «Доказательство минимальным контрпримером» (PDF) . Alpha.math.uga.edu . Архивировано из оригинала (PDF) 17 апреля 2018 г. Проверено 28 ноября 2019 г.
- ^ Льюис, Том (осень 2010 г.). «§20 Наименьший контрпример» (PDF) . math.furman.edu . Проверено 28 ноября 2019 г.
- ^ Фейт, Уолтер ; Томпсон, Джон Г. (1963), «Разрешимость групп нечетного порядка» , Pacific Journal of Mathematics , 13 : 775–1029, doi : 10.2140/pjm.1963.13.775 , ISSN 0030-8730 , MR 0166261
- ^ «Основная теорема арифметики | Делимость и индукция | Подземная математика» . Undergroundmathematics.org . Проверено 28 ноября 2019 г.
- ^ «Основная теорема арифметики» . www.dpmms.cam.ac.uk . Проверено 28 ноября 2019 г.
- ^ Ришар Курант ; Герберт Роббинс (1996). Что такое математика? (2-е изд.). Оксфорд: Издательство Оксфордского университета. ISBN 9780195105193 . Здесь: с.495: "Поскольку нет смысла увеличивать плохие карты, мы идем противоположным путем и смотрим на самые маленькие плохие карты, в просторечии называемые минимальными преступниками".