Введение
Доказательство от противного
В логике доказательство от противного — это метод доказательства, устанавливающий истинность или справедливость утверждения путём показа того, что предположение об его ложности приводит к противоречию. Хотя этот метод широко используется в математических доказательствах, не все математические школы признают этот вид неконструктивного доказательства универсально обоснованным. В более широком смысле, доказательство от противного — это любая форма аргументации, устанавливающая истинность утверждения путём получения противоречия, даже если исходное предположение не является отрицанием доказываемого утверждения. В этом общем смысле доказательство от противного также известно как косвенное доказательство, доказательство предположением об обратном и reductio ad impossibile. Математическое доказательство от противного обычно строится следующим образом:
Утверждение, которое требуется доказать, — это P.
Мы предполагаем, что P ложно, то есть, мы предполагаем ¬P. Затем показывается, что ¬P влечёт за собой ложь. Это обычно достигается путём вывода двух взаимопротиворечивых утверждений, Q и ¬Q, и апелляции к закону непротиворечия. Поскольку предположение о ложности P приводит к противоречию, делается вывод, что P истинно. Важным частным случаем является доказательство существования от противного: чтобы доказать существование объекта с заданным свойством, мы приходим к противоречию из предположения, что все объекты не обладают этим свойством.
We assume P to be false, i. e., we assume ¬P. It is then shown that ¬P implies falsehood. This is typically accomplished by deriving two mutually contradictory assertions, Q and ¬Q, and appealing to the law of noncontradiction. Since assuming P to be false leads to a contradiction, it is concluded that P is in fact true. An important special case is the existence proof by contradiction: in order to demonstrate that an object with a given property exists, we derive a contradiction from the assumption that all objects satisfy the negation of the property.
Закон исключенного середины
Доказательство от противного эквивалентно закону исключённого третьего, впервые сформулированному Аристотелем, который утверждает, что либо высказывание, либо его отрицание истинно, P ∨ ¬P.
Закон не противоречия
Закон непротиворечия был впервые сформулирован как метафизический принцип Аристотелем. Он утверждает, что некоторое высказывание и его отрицание не могут быть одновременно истинными, или, что эквивалентно, высказывание не может быть одновременно истинным и ложным. Формально закон непротиворечия записывается как ¬(P ∧ ¬P) и читается как "неверно, что высказывание является одновременно истинным и ложным". Закон непротиворечия не вытекает из принципа доказательства от противного и не подразумевается им. Законы исключённого третьего и непротиворечия вместе означают, что ровно одно из высказываний P и ¬P истинно.
Бесконечность простых чисел
Теорема Евклида утверждает, что существует бесконечно много простых чисел. В «Началах» Евклида теорема изложена в книге IX, предложение 20: Простых чисел больше, чем любое заданное множество простых чисел. В зависимости от того, как мы формально сформулируем это утверждение, обычное доказательство принимает форму доказательства от противного или опровержения от противного. Мы приводим здесь первое, а ниже – как доказательство можно выполнить как опровержение от противного. Если мы формально выразим теорему Евклида, говоря, что для каждого натурального числа *n* существует простое число, большее *n*, то мы используем доказательство от противного следующим образом. Пусть дано некоторое число *n*. Мы стремимся доказать, что существует простое число, большее *n*. Предположим противное, что такого *p* не существует (применение доказательства от противного). Тогда все простые числа меньше или равны *n*, и мы можем составить список всех из них: *p₁*, *p₂*, ..., *pₖ*. Пусть *P* = *p₁* *p₂* ... *pₖ* – произведение всех простых чисел. Поскольку *P* больше всех простых чисел, оно само не является простым, следовательно, оно должно делиться на одно из них, скажем, *pᵢ*. Тогда и *P*, и *n* делятся на *pᵢ*, следовательно, их разность *P* - *n* также делится на *pᵢ*. Но это невозможно, поскольку 1 не делится ни на одно простое число. Следовательно, мы пришли к противоречию, и значит, существует простое число, большее *n*.
Prime numbers are more than any assigned multitude of prime numbers. Depending on how we formally write the above statement, the usual proof takes either the form of a proof by contradiction or a refutation by contradiction. We present here the former, see below how the proof is done as refutation by contradiction. If we formally express Euclid's theorem as saying that for every natural number there is a prime bigger than it, then we employ proof by contradiction, as follows. Given any number , we seek to prove that there is a prime larger than Suppose to the contrary that no such p exists (an application of proof by contradiction). Then all primes are smaller than or equal to , and we may form the list of them all. Let be the product of all primes and Because is larger than all prime numbers it is not prime, hence it must be divisible by one of them, say Now both and are divisible by , hence so is their difference , but this cannot be because 1 is not divisible by any primes. Hence we have a contradiction and so there is a prime number bigger than
Примеры опровержений посредством противоречия
Следующие примеры обычно называют доказательствами от противного, но формально используют опровержение с помощью противоречия (и, следовательно, являются интуиционистски допустимыми).
Ирациональность квадратного корня из 2
Классическое доказательство того, что квадратный корень из 2 иррационален, является доказательством от противного. Действительно, мы пытаемся доказать отрицание утверждения о существовании a и b, таких что a/b = √2, предположив, что существуют натуральные числа a и b, чье отношение равно квадратному корню из двух, и приходим к противоречию.
Парадокс Рассела
Парадокс Рассела, формулируемый в теории множеств как "не существует множества, элементами которого являются исключительно те множества, которые не содержат сами себя", является отрицанием, обычное доказательство которого представляет собой доказательство от противного.
Обозначение
Доказательства от противного иногда заканчиваются словом "Противоречие!". Исаак Барроу и Баерман использовали обозначение Q. E. A., для "quod est absurdum" ("что есть абсурдное"), по аналогии с Q. E. D., но это обозначение сегодня встречается редко. Графический символ, иногда используемый для обозначения противоречия, — это символ "молнии" в виде нисходящего зигзага (U+21AF: ↯), например, у Дейви и Пристли. Также иногда используются пара противоположно направленных стрелок (как или ), перечеркнутые стрелки, стилизованная форма решётки (например, U+2A33: ⨳), или "знак референции" (U+203B: ※), или .
Мнение Харди
Г. Х. Харди описал доказательство от противного как "одно из самых мощных орудий в арсенале математика", говоря: "Это гораздо более изящный гамбит, чем любой шахматный: шахматист может пожертвовать пешкой или даже фигурой, но математик жертвует всей игрой".
Автоматическое доказательство теоремы
В автоматическом доказательстве теорем метод резолюций основан на доказательстве от противного. То есть, чтобы показать, что данное утверждение следует из заданных гипотез, автоматический решатель предполагает эти гипотезы и отрицание утверждения, и пытается вывести противоречие.