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

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

${\displaystyle {\dfrac {\begin{matrix}\left[{\mathcal {\neg A}}\right]&&\left[{\mathcal {\neg A}}\right]\\{\mathcal {B}}&&{\mathcal {\neg B}}\end{matrix}}{\mathcal {A}}}.}$

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

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

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

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

Это рассуждение можно заменить следующим рассуждением, состоящим из двух частей: первая часть представляет собой доказательство утверждения ${\displaystyle {\mathcal {\neg \neg A}}}$ приведением к нелепости (reductio ad absurdum), а вторая — переход к утверждению ${\displaystyle {\mathcal {A}}}$ снятием двойного отрицания. Поскольку, хотя и неявно, используется классическое правило снятия двойного отрицания, метод доказательства от противного является классическим и служит источником неэффективных доказательств теорем существования. О сущности различий между этими правилами написано далее в данной статье.

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

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

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

— — — - — - — — — - — - — — — - — - — — — - — - — — — - — - — — — - — - — -

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

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

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

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

${\displaystyle {\dfrac {{\text{Г}},{\mathcal {\neg A}}\Rightarrow {\mathcal {B}}{\text{ и Г}},{\mathcal {\neg A}}\Rightarrow {\mathcal {\neg B}}}{{\text{Г}}\Rightarrow {\mathcal {A}}}}.}$

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

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

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

Итак, для того чтобы доказать отрицательное утверждение ${\displaystyle {\mathcal {\neg A}}}$, допускаем, что имеет место ${\displaystyle {\mathcal {A}}}$, и выводим из этого некоторое противоречие: ${\displaystyle {\mathcal {B}}}$ и ${\displaystyle {\mathcal {\neg B}}}$. Неформальная схема, описывающая такой ход рассуждений, выглядит так:

${\displaystyle {\dfrac {{\text{Г}},{\mathcal {A}}\Rightarrow {\mathcal {B}}{\text{ и Г}},{\mathcal {A}}\Rightarrow {\mathcal {\neg B}}}{{\text{Г}}\Rightarrow {\mathcal {\neg A}}}}.}$

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

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

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

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

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

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

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

${\displaystyle {\dfrac {{\text{Г}},{\mathcal {\neg A}}\Rightarrow {\mathcal {B}}{\text{ и Г}},{\mathcal {\neg A}}\Rightarrow {\mathcal {\neg B}}}{{\text{Г}}\Rightarrow {\mathcal {A}}}}}$

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

доказательства приведением к нелепости ${\displaystyle {\dfrac {{\text{Г}},{\mathcal {A}}\Rightarrow {\mathcal {B}}{\text{ и Г}},{\mathcal {A}}\Rightarrow {\mathcal {\neg B}}}{{\text{Г}}\Rightarrow {\mathcal {\neg A}}}}}$

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

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

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

Дело в том, что такие логические законы, как закон исключённого третьего ${\displaystyle {\mathcal {A\vee \neg A}}}$, закон снятия двойного отрицания ${\displaystyle {\mathcal {\neg \neg A\supset A}}}$, схема

${\displaystyle {\dfrac {{\text{Г}},{\mathcal {\neg A}}\Rightarrow {\mathcal {B}}{\text{ и Г}},{\mathcal {\neg A}}\Rightarrow {\mathcal {\neg B}}}{{\text{Г}}\Rightarrow {\mathcal {A}}}}}$

доказательства от противного, приводят к неэффективным конструкциям и доказательствам в математике. В первую очередь это относится к доказательствам так называемых теорем существования, то есть теорем вида: «Существует ${\displaystyle x}$ такой, что ${\displaystyle {\mathcal {P}}\left(x\right)}$»: ${\displaystyle \left(\exists {x}\right){\mathcal {P}}\left(x\right)}$, где ${\displaystyle {\mathcal {P}}\left(x\right)}$ — некоторое свойство ${\displaystyle {\mathcal {P}}}$, которое выполняется для ${\displaystyle x}$, причём ${\displaystyle x}$ пробегает некоторое множество известных объектов (чисел, формул, множеств формул, и т. п.).

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

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

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

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

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

Идея построения основных разделов математики на эффективной основе, без использования закона снятия двойного отрицания и закона исключённого третьего восходит к интуиционистской концепции Л. Э. Я. Брауэра. Интуиционистское направление в математике бурно развивалось на протяжении всего XX в. Существенное развитие неклассические идеи получили в работах представителей школы конструктивного направления в математике во главе с А. А. Марковым — выдающимся советским математиком (1903—1979).

▷ Допустим, что касательная ${\displaystyle p}$ не перпендикулярна радиусу ${\displaystyle OA}$. {Тогда радиус ${\displaystyle OA}$ является наклонной к прямой ${\displaystyle p}$. Так как перпендикуляр, проведённый из точки к прямой ${\displaystyle p}$, меньше наклонной ${\displaystyle OA}$, то расстояние от точки ${\displaystyle O}$ до прямой ${\displaystyle p}$ меньше радиуса окружности. Известно, что если расстояние от центра окружности до прямой меньше радиуса этой окружности, то прямая и окружность имеют две различные общие точки. Отсюда получаем, что прямая ${\displaystyle p}$ и окружность имеют две различные общие точки. Следовательно, прямая ${\displaystyle p}$ не является касательной к окружности с центром ${\displaystyle O}$.} Получили противоречие с условием: ${\displaystyle p}$ является касательной к окружности с центром ${\displaystyle O}$. Тем самым доказано, что прямая ${\displaystyle p}$ перпендикулярна радиусу ${\displaystyle OA}$. ◀

Это доказательство построено в соответствии со схемой ${\displaystyle {\dfrac {\begin{matrix}\left[{\mathcal {\neg A}}\right]&&\left[{\mathcal {\neg A}}\right]\\{\mathcal {B}}&&{\mathcal {\neg B}}\end{matrix}}{\mathcal {A}}}}$. В качестве ${\displaystyle {\mathcal {A}}}$ выступает предложение «Касательная ${\displaystyle p}$ к окружности с центром ${\displaystyle O}$ перпендикулярна радиусу ${\displaystyle OA}$, проведённому в точку касания ${\displaystyle A}$», в качестве ${\displaystyle {\mathcal {B}}}$ — «Прямая ${\displaystyle p}$ является касательной к окружности с центром ${\displaystyle O}$». Вспомогательное рассуждение ${\displaystyle {\begin{matrix}\left[{\mathcal {\neg A}}\right]\\{\mathcal {B}}\end{matrix}}}$ в этом доказательстве вырождается в одно предложение — предложение ${\displaystyle {\mathcal {B}}}$. Вспомогательное рассуждение ${\displaystyle {\begin{matrix}\left[{\mathcal {\neg A}}\right]\\{\mathcal {\neg B}}\end{matrix}}}$ заключено в фигурные скобки.

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

▷ Пусть на плоскости прямые ${\displaystyle a}$ и ${\displaystyle b}$ параллельны и прямая ${\displaystyle c}$ пересекает прямую ${\displaystyle a}$. Докажем, что прямая ${\displaystyle c}$ пересекает прямую ${\displaystyle b}$. Допустим, что прямая ${\displaystyle c}$ не пересекает прямую ${\displaystyle b}$. {Тогда прямая ${\displaystyle c}$ параллельна прямой ${\displaystyle b}$, которая параллельна прямой ${\displaystyle a}$. Следовательно, прямая ${\displaystyle c}$ параллельна прямой ${\displaystyle a}$.} Получили противоречие с тем, что прямая ${\displaystyle c}$ пересекает прямую ${\displaystyle a}$. Следовательно, прямая ${\displaystyle c}$ пересекает прямую ${\displaystyle b}$.

Таким образом, если на плоскости прямые ${\displaystyle a}$ и ${\displaystyle b}$ параллельны и прямая ${\displaystyle c}$ пересекает прямую ${\displaystyle a}$, то прямая ${\displaystyle c}$ пересекает прямую ${\displaystyle b}$. ◀

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