Доказательство истощением - Proof by exhaustion

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

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

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

В изоморфизме Карри – Ховарда доказательство исчерпанием и анализ случая связаны с сопоставлением с образцом в стиле ML .

Пример

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

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

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

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

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

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

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

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

Кол-во кейсов

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

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

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

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

Примечания