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

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

Принцип

Доказательство от противного основано на закон непротиворечивости как впервые формализованный как метафизический принцип Аристотель. Непротиворечие также является теоремой из логика высказываний. Это означает, что утверждение или математическое утверждение не может быть одновременно истинным и ложным. То есть предложение Q и его отрицание ${ Displaystyle lnot}$ Q ("нет-Q") не могут одновременно быть истинными. При доказательстве от противного показано, что отрицание доказываемого утверждения приводит к такому противоречию. Оно имеет вид сокращение до абсурда аргумент, и обычно происходит следующим образом:

Предложение, которое нужно доказать, п, предполагается ложным. То есть, ${ Displaystyle lnot}$ п правда.
Затем показано, что ${ Displaystyle lnot}$ п следует два взаимно противоречащих друг другу утверждения, Q и ${ Displaystyle lnot}$ Q.
С Q и ${ Displaystyle lnot}$ Q не могут быть оба верными, предположение, что п ложно должно быть неправильно, поэтому п должно быть правдой.

Третий шаг основан на следующих возможных случаях истинности действительного аргумента p → q.

p (T) → q (T), где x в p (x) - значение истинности утверждения p; T означает Истина и F - Ложь.
p (F) → q (T).
p (F) → q (F).

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

Доказательство от противного формулируется как ${ Displaystyle { текст {p}} Equiv { text {p}} vee bot Equiv lnot left ( lnot { text {p}} right) vee bot Equiv lnot { text {p}} to bot}$ , куда ${ displaystyle bot}$ логическое противоречие или ложный утверждение (утверждение, значение истинности которого ложный). Если ${ displaystyle bot}$ достигается из ${ Displaystyle lnot}$ п через правильную логику, тогда ${ displaystyle lnot { text {p}} to bot}$ доказано как истинное, так что p доказано как истинное.

Альтернативная форма доказательства от противного приводит к противоречию с доказываемым утверждением, показывая, что ${ Displaystyle lnot}$ п подразумевает п. Это противоречие, поэтому предположение ${ Displaystyle lnot}$ п должно быть ложным, что эквивалентно п как правда. Это сформулировано как ${ displaystyle { text {p}} Equiv { text {p}} vee { text {p}} Equiv lnot left ( lnot { text {p}} right) vee { text {p}} Equiv lnot { text {p}} to { text {p}}}$ .

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

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

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

{ Displaystyle forall P vdash (P lor lnot P)}

(Для всех предложений п, либо п или нет-п правда)

То есть не существует другого значения истинности, кроме «истинного» и «ложного», которое может принимать предложение. В сочетании с принципом непротиворечивости это означает, что ровно один из ${ displaystyle P}$ и ${ Displaystyle lnot P}$ правда. При доказательстве от противного это позволяет сделать вывод, что, поскольку возможность ${ Displaystyle lnot P}$ был исключен, ${ displaystyle P}$ должно быть правдой.

Закон исключенного третьего принимается практически во всех формальных логиках; однако некоторые интуиционист математики не принимают его и, таким образом, отвергают доказательство от противоречия как жизнеспособный метод доказательства.^[2]

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

Доказательство от противного тесно связано с доказательство контрапозитивным, и их иногда путают, хотя это разные методы. Основное различие состоит в том, что доказательство контрапозитивом применяется только к утверждениям. ${ displaystyle P}$ что можно записать в виде ${ displaystyle A rightarrow B}$ (т. е. импликации), тогда как метод доказательства от противного применяется к утверждениям ${ displaystyle P}$ любой формы:

Доказательство от противного (общее): предполагать ${ Displaystyle lnot P}$ и приходим к противоречию.

Это соответствует, в рамках логика высказываний, к эквивалентности

{ Displaystyle { текст {p}} Equiv { text {p}} vee bot Equiv lnot left ( lnot { text {p}} right) vee bot Equiv lnot { text {p}} to bot}

, куда

{ displaystyle bot}

логическое противоречие или ложный утверждение (утверждение, значение истинности которого ложный).

В случае, если утверждение должно быть доказано является следствие ${ displaystyle A rightarrow B}$ , то различия между прямым доказательством, доказательством противоположным и доказательством от противного можно обозначить следующим образом:

Прямое доказательство: предполагать ${ displaystyle A}$ и показать ${ displaystyle B}$ .
Доказательство контрапозитивным: предполагать ${ Displaystyle lnot B}$ и показать ${ displaystyle lnot A}$ .

Это соответствует эквивалентности

{ Displaystyle A rightarrow B эквив lnot B rightarrow lnot A}

.

Доказательство от противного: предполагать ${ displaystyle A}$ и ${ Displaystyle lnot B}$ и приходим к противоречию.

Это соответствует эквивалентностям

{ displaystyle { text {p}} to { text {q}} Equiv lnot { text {p}} vee { text {q}} Equiv lnot left ({ text { p}} wedge lnot { text {q}} right) Equiv lnot left ({ text {p}} wedge lnot { text {q}} right) vee bot Equiv left ({ text {p}} wedge lnot { text {q}} right) to bot}

.

Примеры

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

Классическим доказательством противоречия из математики является доказательство того, что квадратный корень из 2 иррационален.^[3] Если бы рациональный, это можно было бы выразить как дробь а/б в самые низкие сроки, куда а и б находятся целые числа, по крайней мере один из которых странный. Но если а/б = √2, тогда а² = 2б². Следовательно, а² должно быть четным, а поскольку квадрат нечетного числа нечетный, это, в свою очередь, означает, что а сам по себе - что означает, что б должно быть нечетным, потому что a / b в самом низком смысле.

С другой стороны, если а четно, тогда а² делится на 4. Если а² делится на 4 и а² = 2б², то 2б² делится на 4, поэтому б² должен быть четным, что означает б тоже.

Так б является как нечетным, так и четным; противоречие. Поэтому исходное предположение - что √2 может быть выражено дробью - должно быть ложным.^[4]

Длина гипотенузы

Метод доказательства от противного также использовался, чтобы показать, что для любого невырожденный прямоугольный треугольник, длина гипотенузы меньше суммы длин двух оставшихся сторон.^[5] Позволяя c быть длиной гипотенузы и а и б быть длиной ног, можно также выразить требование более кратко, как а + б > c. В этом случае можно провести доказательство от противного, обратившись к теорема Пифагора.

Во-первых, утверждение отрицается, чтобы предположить, что а + б ≤ c. В этом случае возведение обеих сторон в квадрат даст (а + б)² ≤ c², или эквивалентно, а² + 2ab + б² ≤ c². Треугольник невырожден, если каждое из его ребер имеет положительную длину, поэтому можно считать, что оба а и б больше 0. Следовательно, а² + б² < а² + 2ab + б² ≤ c², а переходное отношение может быть сокращено до а² + б² < c².

С другой стороны, из теоремы Пифагора также известно, что а² + б² = c². Это привело бы к противоречию, поскольку строгое неравенство и равенство взаимоисключающий. Противоречие означает, что оба утверждения не могут быть истинными, и известно, что теорема Пифагора верна. Отсюда следует, что предположение а + б ≤ c должно быть ложным и, следовательно, а + б > c, доказывая иск.

Нет наименьшего положительного рационального числа

Рассмотрим предложение, п: "не существует наименьшего рационального числа больше 0". В доказательстве от противного мы начинаем с предположения противного, ¬п: что там является наименьшее рациональное число, скажем,р.

Сейчас же, р/ 2 - рациональное число больше 0 и меньше р. Но это противоречит предположению, что р был самый маленький рациональное число (если "р наименьшее рациональное число "были Q, тогда можно сделать вывод из "р/ 2 - рациональное число, меньшее, чем р"что ¬Q.) Это противоречие показывает, что исходное предложение, п, должно быть правдой. То есть, что «не существует наименьшего рационального числа больше 0».

Другой

Для других примеров см. доказательство того, что квадратный корень из 2 не является рациональным (где косвенные доказательства, отличные от над можно найти) и Диагональный аргумент Кантора.

Обозначение

Доказательства от противного иногда заканчиваются словом «Противоречие!». Исаак Барроу и Баерман использовал обозначение Q.E.A. для "quod est absurdum"(" что абсурдно "), в соответствии с Q.E.D., но сегодня это обозначение используется редко.^[6]^[7] Графический символ, который иногда используется для обозначения противоречий, - это зигзагообразная стрелка вниз «молния» (U + 21AF: ↯), например, у Дэйви и Пристли.^[8] Другие, иногда используемые, включают пару противоположные стрелки (в качестве ${ Displaystyle rightarrow ! leftarrow}$ или же ${ Displaystyle Rightarrow ! Leftarrow}$ ), зачеркнутые стрелки ( ${ displaystyle nleftrightarrow}$ ), стилизованная форма хеша (например, U + 2A33: ⨳) или «отметка» (U + 203B: ※).^[9]^[10] Также появляется символ "поднятой галочки" (U + 22A5: ⊥), используемый философами и логиками (см. Противоречие), но его часто избегают из-за его использования для ортогональность.

Принцип взрыва

Любопытным логическим следствием принципа непротиворечивости является то, что противоречие подразумевает любое утверждение; если противоречие принято как истинное, любое утверждение (включая его отрицание) может быть доказано на его основе.^[11] Это известно как принцип взрыва (Латинский: ex falso quodlibet, «из лжи [следует] что-нибудь», или ex contraissione sequitur quodlibet, «из противоречия следует все»), или принцип псевдоскота.

{ displaystyle forall Q: (P land lnot P) rightarrow Q}

(для всех Q, P и не-P следует Q)

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

Обнаружение противоречий в основах математики начала ХХ века, таких как Парадокс Рассела, угрожало всей структуре математики из-за принципа взрыва. Это мотивировало большую работу в течение 20-го века по созданию последовательных аксиоматических систем, обеспечивающих логическую основу для математики. Это также привело к тому, что некоторые философы, такие как Ньютон да Коста, Вальтер Карниелли и Грэм Прист отвергнуть принцип непротиворечивости, породив такие теории, как непротиворечивая логика и диалетизм, который принимает, что существуют как истинные, так и ложные утверждения.^[12]

Прием

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

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

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

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

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

[1] "Reductio ad absurdum | логика". Энциклопедия Британника. Получено 2019-10-25.

[2] "Окончательный словарь высшего математического жаргона - доказательство от противного". Математическое хранилище. 2019-08-01. Получено 2019-10-25.

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

[4] «Доказательство от противного». Искусство решения проблем. Получено 2019-10-25.

[5] Стоун, Питер. «Логика, множества и функции: с отличием» (PDF). Материалы курса. стр. 14–23: Департамент компьютерных наук Техасского университета в Остине. Получено 6 февраля 2013.CS1 maint: location (связь)

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

[7] «Окончательный словарь высшего математического жаргона - Q.E.A.» Математическое хранилище. 2019-08-01. Получено 2019-10-25.

[8] Б. Дэйви, Х.А. Пристли, Введение в решетки и порядок, Cambridge University Press, 2002.

[9] Полный список символов LaTeX, стр. 20. http://www.ctan.org/tex-archive/info/symbols/comprehensive/symbols-a4.pdf

[10] Гэри Хардегри, Введение в модальную логику, Глава 2, стр. II – 2. https://web.archive.org/web/20110607061046/http://people.umass.edu/gmhwww/511/pdf/c02.pdf

[Ferguson1-11] Фергюсон, Томас Маколей; Священник, Грэм (2016). Словарь логики. Издательство Оксфордского университета. п. 146. ISBN 978-0192511553.

[12] Карниелли, Вальтер; Маркос, Жоао (2001). «Таксономия C-систем». arXiv:математика / 0108036.

[Hardy-13] Г. Х. Харди, Извинения математика; Издательство Кембриджского университета, 1992. ISBN 9780521427067. PDF стр.19.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]