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

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

В логике доказательство от противного — это форма доказательства , которая устанавливает истинность или обоснованность предложения , показывая, что предположение о том, что предложение ложно, приводит к противоречию . Хотя оно довольно широко используется в математических доказательствах, не каждая школа математической мысли признает этот вид неконструктивного доказательства универсально действительным. ^[1]

В более широком смысле доказательство от противного — это любая форма аргументации, которая устанавливает утверждение путем достижения противоречия, даже если исходное предположение не является отрицанием доказываемого утверждения. В этом общем смысле доказательство от противного также известно как косвенное доказательство , доказательство, предполагающее обратное , ^[2] и доведение до невозможности . ^[3]

Математическое доказательство, использующее доказательство от противного, обычно происходит следующим образом:

1. Предложение, которое необходимо доказать, — это P.
2. Мы предполагаем, что P ложно, т.е. мы предполагаем, что ¬P .
3. Затем показано, что ¬P подразумевает ложность. Обычно это достигается путем вывода двух взаимно противоречивых утверждений, Q и ¬Q , и обращения к закону непротиворечивости .
4. Поскольку предположение, что P ложно, приводит к противоречию, делается вывод, что P на самом деле истинно.

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

Формализация

Этот принцип может быть формально выражен в виде пропозициональной формулы ¬¬P ⇒ P , что эквивалентно (¬P ⇒ ⊥) ⇒ P , которая гласит: «Если предположение, что P ложно, подразумевает ложность, то P истинно».

В естественной дедукции этот принцип принимает форму правила вывода.

${\displaystyle {\cfrac {\vdash \lnot \lnot P}{\vdash P}}}$

который гласит: «Если доказано, то можно сделать вывод». ${\displaystyle \lnot \lnot P}$ ${\displaystyle P}$

В секвенциальном исчислении принцип выражается секвенцией

${\displaystyle \Gamma ,\lnot \lnot P\vdash P,\Delta }$

который гласит: «Гипотезы и влекут за собой заключение или ». ${\displaystyle \Gamma }$ ${\displaystyle \lnot \lnot P}$ ${\displaystyle P}$ ${\displaystyle \Delta }$

Обоснование

В классической логике этот принцип может быть оправдан рассмотрением таблицы истинности предложения ¬¬P ⇒ P , которая показывает, что это тавтология :

Другой способ оправдать этот принцип — вывести его из Закона исключенного третьего следующим образом. Мы предполагаем ¬¬P и пытаемся доказать P . По закону исключенного третьего P либо выполняется, либо нет:

1. если P выполняется, то, конечно, P выполняется.
2. если ¬P выполняется, то мы выводим ложность, применяя закон непротиворечия к ¬P и ¬¬P , после чего принцип взрыва позволяет нам заключить P .

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

В классическом секвенциальном исчислении LK доказательство от противного выводится из правил вывода отрицания:

${\displaystyle {\cfrac {{\cfrac {{\cfrac {\ }{\Gamma ,P\vdash P,\Delta }}\;(I)}{\Gamma ,\vdash \lnot P,P,\Delta }}\;({\lnot }R)}{\Gamma ,\lnot \lnot P\vdash P,\Delta }}\;({\lnot }L)}$

Связь с другими методами доказательства

Опровержение от противного

Доказательство от противного аналогично опровержению от противного , ^{[4] [5]} также известному как доказательство отрицания , которое утверждает, что ¬P доказывается следующим образом:

1. Предложение, которое необходимо доказать, — это ¬P .
2. Предположим , П.
3. Вывести ложь.
4. Заключите ¬P .

Напротив, доказательство от противного происходит следующим образом:

1. Предложение, которое необходимо доказать, — это P.
2. Предположим, ¬P .
3. Вывести ложь.
4. Заключение П. _

Формально это не одно и то же, поскольку опровержение от противного применяется только тогда, когда доказываемое предложение отрицается, тогда как доказательство от противного может быть применено к любому предложению вообще. ^[6] В классической логике, где и могут свободно меняться местами, различие в значительной степени неясно. Таким образом, в математической практике оба принципа называются «доказательством от противного». ${\displaystyle P}$ ${\displaystyle \neg \neg P}$

Закон исключенного третьего

Доказательство от противного эквивалентно закону исключенного третьего , впервые сформулированному Аристотелем , который утверждает, что либо утверждение, либо его отрицание истинно, P ∨ ¬P .

Закон непротиворечия

Закон непротиворечия впервые был сформулирован как метафизический принцип Аристотелем . Он утверждает, что предложение и его отрицание не могут быть одновременно истинными, или, что то же самое, что предложение не может быть одновременно истинным и ложным. Формально закон непротиворечия записывается как ¬(P ∧ ¬P) и читается как «не тот случай, когда предложение одновременно истинно и ложно». Закон непротиворечия не следует и не подразумевается принципом доказательства от противного.

Законы исключенного третьего и непротиворечия вместе означают, что истинно только одно из P и ¬P .

Доказательство от противного в интуиционистской логике

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

Интерпретация доказательства от противного Брауэра – Хейтинга – Колмогорова дает следующее интуиционистское условие справедливости:

«Если не существует метода установить, что предложение ложно, то существует метод, позволяющий установить, что это предложение истинно».

Если под словом «метод» понимать алгоритм , то условие неприемлемо, так как оно позволило бы нам решить проблему остановки . Чтобы увидеть, как это сделать, рассмотрим утверждение H(M) , в котором говорится: « Машина Тьюринга M останавливается или не останавливается». Его отрицание ¬H(M) утверждает, что « M ни останавливается, ни не останавливается», что неверно по закону непротиворечия (который интуитивно верен). Если бы доказательство от противного было интуиционистски допустимым, мы получили бы алгоритм для определения того, останавливается ли произвольная машина Тьюринга M , тем самым нарушая (интуиционистски допустимое) доказательство неразрешимости проблемы остановки .

Предложение P , которое удовлетворяет этому требованию , известно как ¬¬-стабильное предложение . Таким образом, в интуиционистской логике доказательство от противного не является универсально действительным, а может быть применено только к ¬¬-устойчивым суждениям. Пример такого предложения является разрешимым, т. е. удовлетворяющим . Действительно, приведенное выше доказательство того, что закон исключенного третьего подразумевает доказательство от противного, можно перепрофилировать, чтобы показать, что разрешимое предложение ¬¬-стабильно. Типичным примером разрешимого предложения является утверждение, которое можно проверить прямым вычислением, например « является простым» или « делит ». ${\displaystyle \lnot \lnot P\Rightarrow P}$ ${\displaystyle P\lor \lnot P}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle b}$

Примеры доказательств от противного

Элементы Евклида

Раннее появление доказательства от противного можно найти в «Началах» Евклида , книга 1, предложение 6: ^[7]

Если в треугольнике два угла равны, то и стороны, лежащие против равных углов, также равны.

Доказательство продолжается в предположении, что противоположные стороны не равны, и приводит к противоречию.

Nullstellensatz Гильберта

Влиятельное доказательство от противного было дано Дэвидом Гильбертом . В его Nullstellensatz говорится:

Если – многочлены от n неопределенных чисел с комплексными коэффициентами, не имеющие общих комплексных нулей , то существуют многочлены такие, что ${\displaystyle f_{1},\ldots ,f_{k}}$ ${\displaystyle g_{1},\ldots ,g_{k}}$ ${\displaystyle f_{1}g_{1}+\ldots +f_{k}g_{k}=1.}$

Гильберт доказал это утверждение, предположив, что таких многочленов не существует , и пришел к противоречию. ^[8] ${\displaystyle g_{1},\ldots ,g_{k}}$

Бесконечность простых чисел

Теорема Евклида утверждает, что простых чисел бесконечно много. В «Началах» Евклида эта теорема сформулирована в книге IX, предложение 20: ^[9]

Простые числа — это больше, чем любое заданное множество простых чисел.

В зависимости от того, как формально мы напишем приведенное выше утверждение, обычное доказательство принимает либо форму доказательства от противного, либо опровержения от противного. Мы приведем здесь первое, посмотрим ниже, как производится доказательство как опровержение от противного.

Если мы формально выражаем теорему Евклида так, что для каждого натурального числа существует простое число, большее его, то мы используем доказательство от противного следующим образом. ${\displaystyle n}$

Учитывая любое число , мы стремимся доказать, что существует простое число, большее, чем . Предположим противное, что такого p не существует (применение доказательства от противного). Тогда все простые числа меньше или равны , и мы можем сформировать их список. Пусть будет произведением всех простых чисел и . Поскольку оно больше всех простых чисел, оно не является простым, следовательно, оно должно делиться на одно из них, скажем . Теперь оба и делятся на , а значит, и их разница , но этого не может быть, потому что 1 не делится ни на какие простые числа. Следовательно, мы имеем противоречие и, следовательно, существует простое число, большее, чем ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle p_{1},\ldots ,p_{k}}$ ${\displaystyle P=p_{1}\cdot \ldots \cdot p_{k}}$ ${\displaystyle Q=P+1}$ ${\displaystyle Q}$ ${\displaystyle p_{i}}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle p_{i}}$ ${\displaystyle Q-P=1}$ ${\displaystyle n}$

Примеры опровержений от противного

Следующие примеры обычно называют доказательствами от противного, но формально они используют опровержение от противного (и, следовательно, являются интуиционистски действительными). ^[10]

Бесконечность простых чисел

Взглянем еще раз на теорему Евклида – Книга IX, Предложение 20: ^[11]

Простые числа — это больше, чем любое заданное множество простых чисел.

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

Для любого конечного списка простых чисел будет показано, что существует хотя бы одно дополнительное простое число, которого нет в этом списке. Позвольте быть продуктом всех перечисленных простых чисел и простого фактора , возможно самого себя . Мы утверждаем, что его нет в данном списке простых чисел. Предположим, что это было бы наоборот (применение опровержения от противного). Тогда разделил бы оба и , следовательно, и их разность, которая равна . Это дает противоречие, поскольку ни одно простое число не делит 1. ${\displaystyle p_{1},\ldots ,p_{n}}$ ${\displaystyle P=p_{1}\cdot p_{2}\cdots p_{n}}$ ${\displaystyle p}$ ${\displaystyle P+1}$ ${\displaystyle P+1}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle P}$ ${\displaystyle P+1}$ ${\displaystyle 1}$

Иррациональность квадратного корня из 2

Классическое доказательство того, что квадратный корень из 2 иррационален, является опровержением от противного. ^[12] Действительно, мы намеревались доказать отрицание ¬ ∃ a, b ∈ . a/b = √ 2 ${\displaystyle \mathbb {N} }$ , предположив, что существуют натуральные числа a и b , отношение которых равно квадратному корню из двух, и получим противоречие.

Доказательство бесконечным спуском.

Доказательство бесконечным спуском — это метод доказательства, при котором доказывается, что наименьший объект с желаемым свойством не существует следующим образом:

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

Такое доказательство снова является опровержением от противного. Типичным примером является доказательство утверждения «не существует наименьшего положительного рационального числа»: предположим, что существует наименьшее положительное рациональное число q , и выведем противоречие, заметив, чтод/2даже меньше, чем q , и все еще положителен.

Парадокс Рассела

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

Обозначения

Доказательства от противного иногда заканчиваются словом «Противоречие!». Исаак Барроу и Берманн использовали обозначение QEA, что означает « quod est абсурдно » («что абсурдно»), аналогично QED , но сегодня это обозначение используется редко. ^[13] Графический символ, иногда используемый для обозначения противоречий, - это зигзагообразная стрелка, направленная вниз, «молния» (U + 21AF: ↯), например, у Дэйви и Пристли. ^[14] Иногда используются и другие варианты: пара противоположных стрелок (например ^{, [ нужна ссылка ]} или ), ^{[ нужна ссылка ]} зачеркнутые стрелки ( ), ^{[ нужна ссылка ]} стилизованная форма хеша (например, U+2A33: ⨳) , ^{[ нужна ссылка ]} или «референтный знак» (U+203B: ※), ^{[ нужна ссылка ]} или . ^{[15] [16]} ${\displaystyle \rightarrow \!\leftarrow }$ ${\displaystyle \Rightarrow \!\Leftarrow }$ ${\displaystyle \nleftrightarrow }$ ${\displaystyle \times \!\!\!\!\times }$

Взгляд Харди

Г.Х. Харди назвал доказательство от противного «одним из лучших орудий математика», заявив: «Это гораздо более тонкий гамбит, чем любой шахматный гамбит : шахматист может предложить жертву пешки или даже фигуры, но математик предлагает игру». ." ^[17]

Автоматизированное доказательство теорем

В автоматизированном доказательстве теорем метод разрешения основан на доказательстве от противного. То есть, чтобы показать, что данное утверждение вытекает из данных гипотез, автоматизированное средство доказательства предполагает гипотезы и отрицание утверждения и пытается вывести противоречие. ^[18]

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

• Закон исключенного третьего
• Закон непротиворечия
• Доказательство исчерпанием
• Доказательство бесконечным спуском.
• Модус толленс
• Доведение до абсурда

Рекомендации

1. Бишоп, Эрретт 1967. Основы конструктивного анализа , Нью-Йорк: Academic Press. ISBN  4-87187-714-0
2. «Доказательство от противного». www2.edc.org . Проверено 12 июня 2023 г.
3. "Доведение до абсурда | логика" . Британская энциклопедия . Проверено 25 октября 2019 г.
4. «Доказательство от противного». нЛаб . Проверено 7 октября 2022 г.
5. Ричард Хаммак, Книга доказательств , 3-е издание, 2022 г., ISBN 978-0-9894721-2-8 ; см. «Глава 9: Опровержение». 
6. Бауэр, Андрей (29 марта 2010 г.). «Доказательство отрицания и доказательство от противного». Математика и вычисления . Проверено 26 октября 2021 г.
7. «Элементы Евклида, Книга 6, Предложение 1» . Проверено 2 октября 2022 г.
8. Гильберт, Дэвид (1893). «Ueber die vollen Invariantensysteme» . Математические Аннален . 42 (3): 313–373. дои : 10.1007/BF01444162.
9. «Элементы Евклида, Книга 9, Предложение 20» . Проверено 2 октября 2022 г.
10. Бауэр, Андрей (2017). «Пять этапов принятия конструктивной математики». Бык. амер. Математика. Соц. 54 (2017), 481-498 . Проверено 2 октября 2022 г.
11. «Элементы Евклида, Книга 9, Предложение 20» . Проверено 2 октября 2022 г.
12. Альфельд, Питер (16 августа 1996 г.). «Почему квадратный корень из 2 иррационален?». Понимание математики, учебное пособие . Департамент математики Университета Юты . Проверено 6 февраля 2013 г.
13. «Обсуждения на математическом форуме» .
14. Б. Дэйви и Х. А. Пристли, Введение в решетки и порядок , издательство Кембриджского университета, 2002; см. «Указатель обозначений», с. 286.
15. Гэри Харградус, Введение в модальную логику , глава 2, стр. II–2. https://web.archive.org/web/20110607061046/http://people.umass.edu/gmhwww/511/pdf/c02.pdf
16. Полный список символов LaTeX, стр. 20. http://www.ctan.org/tex-archive/info/symbols/comprehensive/symbols-a4.pdf.
17. GH Hardy , Извинение математика ; Издательство Кембриджского университета, 1992. ISBN 9780521427067 .  PDF стр. 19. Архивировано 16 февраля 2021 г. в Wayback Machine .
18. «Линейное разрешение», От логики к логическому программированию , MIT Press, 1994 , получено 21 декабря 2023 г.

Дальнейшее чтение и внешние ссылки

• Франклин, Джеймс ; Дауд, Альберт (2011). Доказательство по математике: Введение. Глава 6: Кью. ISBN 978-0-646-54509-7.{{cite book}}: CS1 maint: location (link)
• Доказательство от противного из книги Ларри В. Кьюсика «Как писать доказательства»
• Интернет-энциклопедия философии Reductio ad Absurdum; ISSN 2161-0002