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

Доказательство «от противного» (лат. contradictio in contrarium), или апагогическое косвенное доказательство, — вид доказательства, при котором «доказывание» некоторого суждения (тезиса доказательства) осуществляется через опровержение отрицания этого суждения — антитезиса. Этот способ доказательства основывается на истинности закона двойного отрицания в классической логике.

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

Схема доказательства

Схемой доказательства от противного называют схему:

$\frac{\begin{array}{ccc}\left[\mathrm{\neg }{𝒜}\right]& & \left[\mathrm{\neg }{𝒜}\right]\\ {ℬ}& & \mathrm{\neg }{ℬ}\end{array}}{{𝒜}}.$

Она формализует метод доказательства от противного.

Доказательство утверждения ${𝒜}$ проводится следующим образом. Сначала принимают предположение, что утверждение ${𝒜}$ неверно, а затем доказывают, что при таком предположении было бы верно некоторое утверждение ${ℬ}$, которое заведомо неверно.

Из определения импликации следует, что, если ${ℬ}$ ложно, то формула $\mathrm{\neg }{𝒜}{\Rightarrow }{ℬ}$ истинна тогда и только тогда, когда $\mathrm{\neg }{𝒜}$ ложно, следовательно утверждение ${𝒜}$ истинно.

Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение $\mathrm{\neg }\mathrm{\neg }{𝒜}$, которое по закону двойного отрицания равносильно утверждению ${𝒜}$.

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

Замечание. Данная схема похожа на другую — на схему доказательства приведением к нелепости. В связи с этим их часто путают. Однако несмотря на некоторое сходство, они имеют разную форму. Причём различаются они не только по форме, но и по существу, и различие это носит принципиальный характер.

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

Идея необходимости различать эти методы в преподавании математики принадлежит Феликсу Александровичу Кабакову (1927–2008), который проводил эту идею в жизнь на протяжении сорока лет работы на математическом факультете МПГУ.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Перейдём к сопоставлению соответствующих методов доказательств.

Метод доказательства от противного принято считать известным методом доказательства, однако часто термин «доказательство от противного» используется в разных смыслах и применительно к разным методам доказательства. Чаще всего метод доказательства от противного путают с методом доказательства приведением к нелепости.

Буквами ${𝒜}$ и ${ℬ}$ будем обозначать произвольные предложения, а буквой $\text{Г}$ — произвольные конечные множества предложений. Будем использовать запись $\text{Г}\Rightarrow {𝒜}$ для обозначения того факта, что предложение ${𝒜}$ обосновано (доказано), исходя из предложений $\text{Г}$, или ${𝒜}$ логически следует из $\text{Г}$. Отношение $\Rightarrow$ между множествами предложений и предложениями будем называть отношением логического следования.

Метод доказательства от противного заключается в следующем. Пусть требуется доказать предложение ${𝒜}$, исходя из некоторых предложений $\text{Г}$ (это могут быть ранее доказанные теоремы, аксиомы или допущения). Допускаем, что ${𝒜}$ неверно, т. е. допускаем $\mathrm{\neg }{𝒜}$, и путём рассуждений, исходя из $\text{Г}$ и $\mathrm{\neg }{𝒜}$, выводим противоречие, т. е. предложение ${ℬ}$ и его отрицание $\mathrm{\neg }{ℬ}$. После этого мы заключаем, что допущение неверно, а значит, верно предложение ${𝒜}$. Наше рассуждение можно описать с помощью следующей неформальной схемы рассуждений:

$\frac{\text{Г},\mathrm{\neg }{𝒜}\Rightarrow {ℬ}\text{ и Г},\mathrm{\neg }{𝒜}\Rightarrow \mathrm{\neg }{ℬ}}{\text{Г}\Rightarrow {𝒜}}.$

Именно эту схему следует называть схемой доказательства от противного.

Ситуация меняется, когда нужно опровергнуть предложение ${𝒜}$, другими словами, когда предложение, которое требуется доказать, имеет вид $\mathrm{\neg }{𝒜}$ (не ${𝒜}$), т. е. является отрицательным предложением.

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

Итак, для того чтобы доказать отрицательное утверждение

$\mathrm{\neg }{𝒜}$

, допускаем, что имеет место

${𝒜}$

, и выводим из этого некоторое противоречие:

${ℬ}$

и

$\mathrm{\neg }{ℬ}$

. Неформальная схема, описывающая такой ход рассуждений, выглядит так:

$\frac{\text{Г},{𝒜}\Rightarrow {ℬ}\text{ и Г},{𝒜}\Rightarrow \mathrm{\neg }{ℬ}}{\text{Г}\Rightarrow \mathrm{\neg }{𝒜}}.$

Эту неформальную схему рассуждений принято называть схемой доказательства приведением к нелепости или приведением к абсурду (от лат. reductio ad absurdum).

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

Остановимся на причинах того, почему всё же следует различать эти схемы.

Во-первых, очевидно, что эти схемы отличаются чисто графически, а значит, рассуждения по этим схемам различаются по форме. Различия такого же характера, т. е. по крайней мере по форме, имеются между предложениями ${𝒜}$ и $\mathrm{\neg }\mathrm{\neg }{𝒜}$ (или между предложениями ${𝒜}{\to }{ℬ}$ и $\mathrm{\neg }{𝒜}\vee {ℬ}$). Даже если, находясь на классических позициях, мы считаем, что эти утверждения равносильны, то всё равно факт различия по форме является очевидным.

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

Ответить на первый вопрос: «Равносильны ли схемы contradictio in contrarium и reductio ad absurdum?» можно на неформальном уровне, не переходя на путь построения формальной логической системы. Связь между данными схемами устанавливается следующим утверждением.

❗УТВЕРЖДЕНИЕ. Схема доказательства от противного

$\frac{\text{Г},\mathrm{\neg }{𝒜}\Rightarrow {ℬ}\text{ и Г},\mathrm{\neg }{𝒜}\Rightarrow \mathrm{\neg }{ℬ}}{\text{Г}\Rightarrow {𝒜}}$

равносильна совокупности двух систем:

доказательства приведением к нелепости $\frac{\text{Г},{𝒜}\Rightarrow {ℬ}\text{ и Г},{𝒜}\Rightarrow \mathrm{\neg }{ℬ}}{\text{Г}\Rightarrow \mathrm{\neg }{𝒜}}$

и снятия двойного отрицания $\mathrm{\neg }\mathrm{\neg }{𝒜}\Rightarrow {𝒜}.$

Доказательство этого утверждения можно найти в книге .

Доказывая методом от противного, мы используем более сильные логические средства, чем когда доказываем приведением к нелепости. Это вызвано тем, что доказательство от противного существенно опирается на правило снятия двойного отрицания, а доказательство приведением к нелепости — нет. Именно благодаря этому обстоятельству различие между схемами contradictio in contrarium и reductio ad absurdum — это различие не только по форме, но и по существу. Более того, это различие тесно связано с некоторыми проблемами оснований математики.

Дело в том, что такие логические законы, как закон исключённого третьего

${𝒜}{\vee }\mathrm{\neg }{𝒜}$

, закон снятия двойного отрицания

$\mathrm{\neg }\mathrm{\neg }{𝒜}{\supset }{𝒜}$

, схема

$\frac{\text{Г},\mathrm{\neg }{𝒜}\Rightarrow {ℬ}\text{ и Г},\mathrm{\neg }{𝒜}\Rightarrow \mathrm{\neg }{ℬ}}{\text{Г}\Rightarrow {𝒜}}$

доказательства от противного, приводят к неэффективным конструкциям и доказательствам в математике. В первую очередь это относится к доказательствам так называемых теорем существования, т. е. теорем вида: «Существует

$x$

такой, что

${𝒫}\left(x\right)$

»:

$\left(\mathrm{\exists }x\right){𝒫}\left(x\right)$

, где

${𝒫}\left(x\right)$

— некоторое свойство

${𝒫}$

, которое выполняется для

$x$

, причём

$x$

пробегает некоторое множество известных объектов (чисел, формул, множеств формул, и т. п.).

Эффективным доказательством теоремы вида $\left(\mathrm{\exists }x\right){𝒫}\left(x\right)$ называется построение объекта $x$ (или способа, позволяющего построить этот объект) и доказательство того, что этот объект действительно обладает требуемым свойством ${𝒫}$. Доказательство теоремы существования, не удовлетворяющее этим условиям, считают неэффективным.

Типичным неэффективным доказательством теоремы существования является доказательство методом от противного. Действительно, пусть требуется доказать утверждение вида $\left(\mathrm{\exists }x\right){𝒫}\left(x\right)$ — «существует объект $x$, обладающий свойством ${𝒫}$». Допустим, что $\mathrm{\neg }\left(\mathrm{\exists }x\right){𝒫}\left(x\right)$. Путём рассуждений получаем некоторое противоречие: ${ℬ}$ и $\mathrm{\neg }{ℬ}$. Отсюда, в силу схемы reductio ad absurdum, делаем вывод, что допущение неверно, т. е. $\mathrm{\neg }\mathrm{\neg }\left(\mathrm{\exists }x\right){𝒫}\left(x\right)$. Далее, снимая двойное отрицание, получим $\left(\mathrm{\exists }x\right){𝒫}\left(x\right)$ и считаем доказательство завершённым. Однако такое доказательство не завершается построением хотя бы одного объекта с требуемым свойством, оно нисколько не приближает нас к построению примера такого $x$, что ${𝒫}\left(x\right)$, т. е. является неэффективным доказательством.

Примерами доказательств такого вида служат доказательства теорем: теоремы об ограниченности непрерывной на отрезке функции (т. е. о существовании верней и нижней границ непрерывной на отрезке функции); теоремы о существовании наибольшего и наименьшего значений у непрерывной на отрезке функции. Традиционное доказательство этих теорем методом от противного не содержит конструкции, позволяющей построить объект, о существовании которого идёт речь в теореме.

Неэффективные доказательства теорем существования признаются не всеми математиками. Для математиков, стоящих на традиционных классических позициях, характерным является признание без всяких ограничений закона исключённого третьего ${𝒜}{\vee }\mathrm{\neg }{𝒜}$ и закона снятия двойного отрицания $\mathrm{\neg }\mathrm{\neg }{𝒜}{\supset }{𝒜}$. Они пренебрегают различиями между утверждениями $\left(\mathrm{\exists }x\right){𝒫}\left(x\right)$ и $\mathrm{\neg }\mathrm{\neg }\left(\mathrm{\exists }x\right){𝒫}\left(x\right)$. Математики, не придерживающиеся классических взглядов (интуиционисты и конструктивисты), отрицают универсальность этих законов. Различия между утверждениями $\left(\mathrm{\exists }x\right){𝒫}\left(x\right)$ и $\mathrm{\neg }\mathrm{\neg }\left(\mathrm{\exists }x\right){𝒫}\left(x\right)$ такие математики признают весьма существенными, считая утверждение $\mathrm{\neg }\mathrm{\neg }\left(\mathrm{\exists }x\right){𝒫}\left(x\right)$, вообще говоря, более слабым, чем $\left(\mathrm{\exists }x\right){𝒫}\left(x\right)$. Доказательство от противного, с их точки зрения, также является неприемлемым, поскольку оно опирается на принцип снятия двойного отрицания.

Таким образом, различие между схемами contradictio in contrarium и reductio ad absurdum носит методологический характер, затрагивая проблему разного понимания утверждений о существовании в математике, а также связанные с эти другие проблемы оснований математики.

Примеры

В математике

Доказательство иррациональности числа $\sqrt{2}$.

Допустим противное: число $\sqrt{2}$ рационально, то есть представляется в виде несократимой дроби $\frac{m}{n}$, где $m$ — целое число, а $n$ — натуральное. Возведём предполагаемое равенство в квадрат:

$\sqrt{2}=\frac{m}{n}$ $\Rightarrow$ $2=\frac{m^2}{n^2}$, откуда $m^2=2n^2$.

Отсюда следует, что $m^2$ чётно, значит, чётно и $m$; следовательно, $m^2$ делится на 4, а значит, $n^2$ и $n$ тоже чётны. Полученное утверждение противоречит несократимости дроби $\frac{m}{n}$. Значит, исходное предположение было неверным, и $\sqrt{2}$ — иррациональное число.

В повседневной жизни

Врач, разъясняя пациенту что тот не болен гриппом, может использовать такие рассуждения: «Если бы вы действительно были больны гриппом, то у вас была бы повышена температура, был заложен нос и т. д. Но всё это у вас отсутствует, значит, нет и гриппа».

Литература

• Тимофеева И. Л. Математическая логика. Курс лекций : Учеб. пособие для студентов вузов. — 2-е изд., перераб. — М. : КДУ, 2007. — 304 с. — ISBN 978-5-98227-307-9.

См. также

• Приведение к абсурду (апагогия)
• Метод бесконечного спуска