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

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

Принцип

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

Предполагается, что доказываемое предложение P неверно. То есть P верно. ${\ Displaystyle \ lnot}$
Затем показано , что Р предполагает два противоречащих друг другу утверждения, Q и Q . ${\ Displaystyle \ lnot}$ ${\ Displaystyle \ lnot}$
Поскольку 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 \ эквив \ lnot \ left (\ lnot {\ text {p}} \ right) \ vee \ bot \ эквив \ 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, приведенное ниже. ${\ displaystyle \ lnot P}$ ${\ displaystyle P}$ ${\ displaystyle P}$

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

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

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

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

{\ displaystyle {\ text {p}} \ Equiv {\ text {p}} \ vee \ bot \ эквив \ lnot \ left (\ lnot {\ text {p}} \ right) \ vee \ bot \ эквив \ 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 иррационален . Если бы он был рациональным , его можно было бы выразить как дробь a / b в наименьших числах , где a и b - целые числа , по крайней мере одно из которых нечетное . Но если a / b = √ 2 , то a ² = 2 b ² . Поэтому ² должна быть ровной, и потому , что квадрат нечетного числа нечетно, что в свою очередь означает , что сама еще - это означает , что б должно быть нечетным , так как / б в условиях низких.

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

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

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

Метод доказательства от противного также использовался, чтобы показать, что для любого невырожденного прямоугольного треугольника длина гипотенузы меньше суммы длин двух оставшихся сторон. Допустим, что 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 , но сегодня это обозначение используется редко. Графический символ, который иногда используется для обозначения противоречий, - это зигзагообразная стрелка вниз «молния» (U + 21AF: ↯), например, у Дэйви и Пристли. Другие, которые иногда используются, включают пару противоположных стрелок (как или ), зачеркнутые стрелки ( ), стилизованную форму решетки (например, U + 2A33: ⨳) или «контрольную метку» (U + 203B: ※). ${\ Displaystyle \ rightarrow \! \ leftarrow}$ ${\ Displaystyle \ Rightarrow \! \ Leftarrow}$ ${\ displaystyle \ nleftrightarrow}$

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

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

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

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

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

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

Прием

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

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

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

использованная литература

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

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

Languages

In other projects