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

В логике к доказательство от противного — это форма доказательства , которая устанавливает истинность или обоснованность предложения приводит , показывая, что предположение о том, что предложение ложно, противоречию . Хотя он довольно широко используется в математических доказательствах, не каждая школа математической мысли признает этот вид неконструктивного доказательства универсально действительным. ^[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: ^[11]

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

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

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

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

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

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

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

Парадокс Рассела [ править ]

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

Обозначения [ править ]

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

Взгляд Харди [ править ]

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

Автоматическое доказательство теорем [ править ]

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

См. также [ править ]

Ссылки [ править ]

^ Бишоп, Эрретт 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 .
^ «Начала Евклида, книга 9, предложение 20» . Проверено 2 октября 2022 г.
^ Бауэр, Андрей (2017). «Пять этапов принятия конструктивной математики» . Бюллетень Американского математического общества . 54 (3): 481–498. дои : 10.1090/bull/1556 . Проверено 2 октября 2022 г.
^ «Начала Евклида, книга 9, предложение 20» . Проверено 2 октября 2022 г.
^ Альфельд, Питер (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, 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 .

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

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

[Hardy-17] GH Hardy , Извинение математика ; Издательство Кембриджского университета, 1992. ISBN 9780521427067 . PDF стр. 19. Архивировано 16 февраля 2021 г. в Wayback Machine .

[18] «Линейное разрешение» , От логики к логическому программированию , MIT Press, 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]

[18]

Формализация [ править ]

Обоснование [ править ]

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

Опровержение от противного [ править ]

Закон исключенного третьего [ править ]

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

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

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

Элементы Евклида [ править ]

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

Бесконечность простых чисел [ править ]

Примеры опровержений от противного [ править ]

Бесконечность простых чисел [ править ]

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

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

Парадокс Рассела [ править ]

Обозначения [ править ]

Взгляд Харди [ править ]

Автоматическое доказательство теорем [ править ]

См. также [ править ]

Ссылки [ править ]

Дальнейшее чтение и внешние ссылки [ править ]

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