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

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

Принцип [ править ]

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

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

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

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

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

Доказательство от противоречия формулируется как , где - логическое противоречие или ложное утверждение (утверждение, истинность которого ложна ). Если достигается из P с помощью действующей логики, то доказывается как истинное, так что p доказывается как истинное.${\displaystyle {\text{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 означает P . Это противоречие, поэтому предположение P должно быть ложным, что эквивалентно 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}}}$

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

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

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

${\displaystyle \forall P\vdash (P\lor \lnot P)}$

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

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

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

Если доказываемое утверждение имеет форму отрицания , доказательство от противоречия может начинаться с предположения, что оно истинно, и вывести противоречие из этого предположения. Из этого следует, что предположение было неверным, а значит, и ложным - QED В таких случаях доказательство не нуждается в апелляции к закону исключенного третьего. Примером является приведенное ниже доказательство иррациональности квадратного корня из 2 .${\displaystyle \lnot P}$${\displaystyle P}$${\displaystyle P}$

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

В этом разделе не процитировать любые источники . Пожалуйста, помогите улучшить этот раздел , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален . ( Январь 2017 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

• Доказательство от противного (общее) : предположим и получим противоречие.${\displaystyle \lnot P}$

Это соответствует, в рамках логики высказываний , эквивалентности , где есть логическое противоречие или ложное утверждение (утверждение, значение истинности которого ложно ).${\displaystyle {\text{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\equiv \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] Если бы это было рационально , это можно было бы выразить как дробь a / b в наименьшем значении , где a и b - целые числа , по крайней мере одно из которых нечетное . Но если a / b = √ 2 , то a ² = 2 b ² . Поэтому ² должна быть ровной, и потому , что квадрат нечетного числа нечетно, что в свою очередь означает , чтоa сам по себе четный - это означает, что b должно быть нечетным, потому что a / b имеет наименьшее значение.

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

Итак, b одновременно и нечетно, и четно; противоречие. Следовательно, первоначальное предположение о том, что √ 2 можно выразить дробью, должно быть ложным. ^[4]

Длина гипотенузы [ править ]

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

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

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

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

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

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

Другое [ править ]

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

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

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

Принцип взрыва [ править ]

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

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

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

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

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

Прием [ править ]

Этот раздел может придать чрезмерный вес определенным идеям, инцидентам или противоречиям . Пожалуйста, помогите создать более сбалансированную презентацию . Обсудите и устраните эту проблему, прежде чем удалять это сообщение. (Май 2020 г.)

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

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

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

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

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

В Викиучебнике « Математическое доказательство» есть страница по теме « Доказательство от противного».

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