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