Доказательство исчерпанием

Доказательство исчерпыванием , также известное как доказательство по случаям , доказательство по анализу случаев , полная индукция или метод грубой силы , представляет собой метод математического доказательства , в котором доказываемое утверждение разбивается на конечное число случаев или наборов эквивалентных случаев. , и где каждый тип случая проверяется, чтобы убедиться, что рассматриваемое предложение верно. ^[1] Это метод прямого доказательства . Доказательство методом исчерпывания обычно состоит из двух этапов:

Доказательство того, что набор случаев является исчерпывающим; т. е. каждый экземпляр доказываемого утверждения соответствует условиям (по крайней мере) одного из случаев.
Доказательства каждого из случаев.

Распространение цифровых компьютеров значительно повысило удобство использования метода исчерпывания (например, первое компьютерное доказательство теоремы о четырех цветах в 1976 году), хотя такие подходы также могут быть оспорены на основе математической элегантности . Экспертные системы могут использоваться для получения ответов на многие поставленные перед ними вопросы. Теоретически доказательство методом исчерпывания можно использовать всякий раз, когда число случаев конечно. Однако, поскольку большинство математических наборов бесконечны, этот метод редко используется для получения общих математических результатов. ^[2]

В изоморфизме Карри-Ховарда доказательство путем исчерпывания и анализ случаев связаны с сопоставлением шаблонов в стиле ML . ^{[ нужна цитата ]}

Пример

Доказательство методом исчерпывания можно использовать, чтобы доказать, что если целое число является идеальным кубом , то оно должно быть либо кратно 9, либо на 1 больше, чем кратно 9, либо на 1 меньше, чем кратно 9. ^[3]

Доказательство :
каждый совершенный куб является кубом некоторого целого числа n , где n либо кратно 3, либо на 1 больше, чем кратно 3, либо на 1 меньше, чем кратно 3. Таким образом, эти три случая являются исчерпывающими:

Случай 1: Если n = 3 p , то n ³ = 27 p ³ , что кратно 9.
Случай 2: Если n = 3 p + 1, то n ³ = 27 p ³ + 27 p ² + 9 p + 1, что на 1 больше, чем кратное 9. Например, если n = 4, то n ³ = 64. = 9×7 + 1.
Случай 3: Если n = 3 p − 1, то n ³ = 27 p ³ − 27 p ² + 9 p − 1, что на 1 меньше кратного 9. Например, если n = 5, то n ³ = 125. = 9×14 − 1. КЭД

Элегантность

Математики предпочитают избегать доказательств путем исчерпывания большого числа случаев, что считается неэлегантным . Иллюстрацией того, насколько неэлегантными могут быть такие доказательства, являются следующие доказательства того, что все современные летние Олимпийские игры проводятся в годы, кратные 4:

Доказательство : первые современные летние Олимпийские игры были проведены в 1896 году, а затем каждые 4 года (не считая исключительных ситуаций, например, когда график игр был нарушен Первой мировой войной, Второй мировой войной и пандемией COVID-19 ). Поскольку 1896 = 474 × 4 делится на 4, следующие Олимпийские игры состоятся в году 474 × 4 + 4 = (474 + 1) × 4, что также делится на четыре, и так далее (это доказательство с помощью математической индукции). ). Следовательно, утверждение доказано.

Это утверждение также можно доказать путем исчерпания данных, перечислив все годы, в которых проводились летние Олимпийские игры, и проверив, что каждый из них можно разделить на четыре. Всего по состоянию на 2016 год было проведено 28 летних Олимпийских игр, и это является доказательством исчерпания 28 случаев.

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

Количество случаев

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

Первое доказательство теоремы о четырех цветах было исчерпывающим доказательством с 1834 случаями. ^[4] Это доказательство было спорным, поскольку большинство случаев проверялось с помощью компьютерной программы, а не вручную. Самое короткое известное на сегодняшний день доказательство теоремы о четырех цветах насчитывает более 600 случаев.

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

Доказательство того, что не существует конечной проективной плоскости порядка 10.
Классификация конечных простых групп .
Гипотеза Кеплера .
Булева задача о тройках Пифагора .

Смотрите также

Примечания

^ Рид, Д.А.; Книппинг, К. (2010), Доказательство в математическом образовании: исследования, обучение и преподавание , Sense Publishers, стр. 133, ISBN 978-9460912443.
^ С., Эпп, Сюзанна (1 января 2011 г.). Дискретная математика с приложениями . Брукс/Коул. ISBN 978-0495391326. ОСЛК 970542319.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Глейстер, Элизабет; Глейстер, Пол (сентябрь 2017 г.). «Математический аргумент, язык и доказательство — уровень AS/A 2017» (PDF) . Математическая ассоциация . Проверено 25 октября 2019 г.
^ Аппель, Кеннет; Хакен, Вольфганг; Кох, Джон (1977), «Каждая плоская карта раскрашивается в четыре цвета. II. Сводимость», Illinois Journal of Mathematics , 21 (3): 504, doi : 10.1215/ijm/1256049012 , MR 0543793, Из 1834 конфигураций в 𝓤