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

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

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

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

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

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

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

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

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

{\cfrac {\vdash \lnot \lnot P}{\vdash P}}

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

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

\Gamma ,\lnot \lnot P\vdash P,\Delta

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

Обоснование

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

п	$\negp$	$\neg\negp$	$\neg\negр \Rightarrow п$
Т	Ф	Т	Т
Ф	Т	Ф	Т

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

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

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

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

{\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 доказывается следующим образом:

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

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

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

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

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

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

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

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

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

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

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

Интерпретация доказательства от противного Брауэра-Хейтинга-Колмогорова дает следующее интуиционистское условие достоверности: если не существует метода установления ложности суждения, то существует метод установления истинности суждения. ^{[ объяснить ]}

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

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

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

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

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

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

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

Теорема Гильберта о нулевой точке

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

Если

f_{1},\ldots ,f_{k}

являются многочленами от

n

неопределенных чисел с комплексными коэффициентами, не имеющими общих комплексных нулей , то существуют многочлены

g_{1},\ldots ,g_{k}

такой, что

f_{1}g_{1}+\ldots +f_{k}g_{k}=1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обозначения

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

Взгляд Харди

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

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

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

См. также

Ссылки

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

[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). «О полных инвариантных системах» . Математические летописи . 42 (3): 313–373. дои : 10.1007/BF01444162 .

[mathcs_clarku_edu-9] Jump up to: ^а ^б «Начала Евклида, книга 9, предложение 20» . Проверено 2 октября 2022 г.

[10] Бауэр, Андрей (2017). «Пять этапов принятия конструктивной математики» . Бюллетень Американского математического общества . 54 (3): 481–498. дои : 10.1090/bull/1556 .

[11] Альфельд, Питер (16 августа 1996 г.). «Почему квадратный корень из 2 иррационален?» . Понимание математики, учебное пособие . Департамент математики Университета Юты . Проверено 6 февраля 2013 г.

[12] «Обсуждения на математическом форуме» .

[13] Б. Дэйви и Х. А. Пристли, Введение в решетки и порядок , издательство Кембриджского университета, 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 .

[Hardy-16] GH Hardy , Извинение математика ; Издательство Кембриджского университета, 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 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]