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

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

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

В более широком смысле, доказательство от противного — это любая форма аргумента, которая устанавливает утверждение, приходя к противоречию, даже когда первоначальное предположение не является отрицанием доказываемого утверждения. В этом общем смысле доказательство от противного также известно как косвенное доказательство , доказательство путем предположения противоположного , ^[2] и reductio ad impossibile . ^[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. Оказывается, что, наоборот, доказательство от противного можно использовать для вывода закона исключенного третьего.

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

${\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: ^[9]

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

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

Для любого конечного списка простых чисел будет показано, что существует по крайней мере одно дополнительное простое число, не входящее в этот список. Пусть будет произведением всех перечисленных простых чисел и простым множителем , возможно, самого себя . Мы утверждаем, что не входит в данный список простых чисел. Предположим противное, что это так (применение опровержения от противного). Тогда делило бы и , следовательно, и их разность, которая равна . Это дает противоречие, поскольку никакое простое число не делит 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 иррационален, является опровержением от противного. ^[11] Действительно, мы намереваемся доказать отрицание ¬ ∃ a, b ∈ . a/b = √ 2 ${\displaystyle \mathbb {N} }$ , предположив, что существуют натуральные числа a и b , отношение которых равно квадратному корню из двух, и выводим противоречие.

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

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

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

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

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

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

Обозначение

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

Точка зрения Харди

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

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

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

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

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

Ссылки

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

Дополнительная литература и внешние ссылки

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