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