Доведение до абсурда

Схемой доказательства приведением к нелепости называют схему, хорошо известную как схему введения отрицания ${\displaystyle \left({\mathcal {\neg B}}\right)}$:

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

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

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

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

Метод приведения к абсурду используется в математической логике в виде умозаключения^[5]. Если требуется доказать истинность некоторого утверждения ${\displaystyle A}$, то образуют отрицание этого утверждения ${\displaystyle {\overline {A}}}$ и находят такое утверждение ${\displaystyle B}$, что оказывается возможным одновременно доказать выводимости ${\displaystyle {\overline {A}}\vdash B}$ и ${\displaystyle {\overline {A}}\vdash {\overline {B}}}$, то есть прийти к абсурду. На основании этого делают логическое заключение, что утверждение ${\displaystyle A}$ истинно.

Метод приведения к абсурду основан на тождественно истинном высказывании: ${\displaystyle (({\overline {A}}\Rightarrow B)\land ({\overline {A}}\Rightarrow {\overline {B}}))\Rightarrow A}$. Следовательно, формула ${\displaystyle A}$ выводима из формул ${\displaystyle {\overline {A}}\Rightarrow B}$ и ${\displaystyle {\overline {A}}\Rightarrow {\overline {B}}}$.

Идея необходимости различать эти методы в преподавании математики принадлежит Феликсу Александровичу Кабакову (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}}.}$

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

Доказывая методом от противного, мы используем более сильные логические средства, чем когда доказываем приведением к нелепости. Это вызвано тем, что доказательство от противного существенно опирается на правило снятия двойного отрицания, а доказательство приведением к нелепости нет. Именно благодаря этому обстоятельству различие между схемами 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 m}$ и ${\displaystyle n}$ — произвольные натуральные числа^[8].^[9] Сначала докажем приведением к нелепости такое утверждение.

▷ Допустим, что ${\displaystyle {\text{НОД}}\left(m,\,n\right)=1}$ и ${\displaystyle {\left({\dfrac {m}{n}}\right)}^{2}=2}$. Из того, что ${\displaystyle {\left({\dfrac {m}{n}}\right)}^{2}=2}$, используя свойства делимости, можно вывести, что ${\displaystyle m\;\vdots \;2}$ и ${\displaystyle n\;\vdots \;2}$, а значит, ${\displaystyle {\text{НОД}}\left(m,\,n\right)\neq 1}$, что противоречит допущению ${\displaystyle {\text{НОД}}\left(m,\,n\right)=1}$. Тем самым доказано: ${\displaystyle \neg \left({\text{НОД}}\left(m,\,n\right)=1\;\And \;{\left({\dfrac {m}{n}}\right)}^{2}=2\right)}$. ◀

Если обозначить предложение ${\displaystyle {\text{НОД}}\left(m,\,n\right)=1\;\And \;{\left({\dfrac {m}{n}}\right)}^{2}=2}$ через ${\displaystyle {\mathcal {A}}}$, а ${\displaystyle {\text{НОД}}\left(m,\,n\right)=1}$ — через ${\displaystyle {\mathcal {B}}}$, станет ясно, что рассуждение проведено в соответствии с одноимённым правилом ${\displaystyle {\dfrac {\begin{matrix}\left[{\mathcal {A}}\right]&&\left[{\mathcal {A}}\right]\\{\mathcal {B}}&&{\mathcal {\neg B}}\end{matrix}}{\mathcal {\neg A}}}}$.

Поскольку рассматриваемое предложение доказано для произвольных натуральных чисел ${\displaystyle m}$ и ${\displaystyle n}$, считаем, что доказано ${\displaystyle \forall m\,\forall n\;\neg \left({\text{НОД}}\left(m,\,n\right)=1\;\And \;{\left({\dfrac {m}{n}}\right)}^{2}=2\right)}$, а значит, и равносильное ему предложение ${\displaystyle \neg \;\exists m\,\exists n\left({\text{НОД}}\left(m,\,n\right)=1\;\And \;{\left({\dfrac {m}{n}}\right)}^{2}=2\right)}$.

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

Тем же методом докажем ещё одно утверждение.

▷ Допустим, что ${\displaystyle \exists r\in \mathbb {Q} \left(r^{2}=2\right)}$. Тогда, в силу определения рационального числа и свойства дроби, ${\displaystyle \exists m\,\exists n\left({\text{НОД}}\left(m,\,n\right)=1\;\And \;{\left({\dfrac {m}{n}}\right)}^{2}=2\right)}$, что противоречит раннее доказанному предложению ${\displaystyle \neg \;\exists m\,\exists n\left({\text{НОД}}\left(m,\,n\right)=1\;\And \;{\left({\dfrac {m}{n}}\right)}^{2}=2\right)}$. Значит, доказано: ${\displaystyle \neg \;\exists r\in \mathbb {Q} \left(r^{2}=2\right)}$. ◀

Теперь если обозначить через ${\displaystyle {\mathcal {A}}}$ предложение ${\displaystyle \exists r\in \mathbb {Q} \left(r^{2}=2\right)}$, а через ${\displaystyle {\mathcal {B}}}$ — предложение ${\displaystyle \exists m\,\exists n\left({\text{НОД}}\left(m,\,n\right)=1\;\And \;{\left({\dfrac {m}{n}}\right)}^{2}=2\right)}$, станет ясно, что последнее рассуждение проведено в соответствии с тем же правилом ${\displaystyle {\dfrac {\begin{matrix}\left[{\mathcal {A}}\right]&&\left[{\mathcal {A}}\right]\\{\mathcal {B}}&&{\mathcal {\neg B}}\end{matrix}}{\mathcal {\neg A}}}}$.

Необходимо различать логическое безэмоциональное упрощение высказывания и приём пропаганды, когда софист опровергает мнение, искусственно усиленное до абсурда.^{[источник не указан 1206 дней]} Также абсурдность обсуждаемого высказывания должна оцениваться в контексте цели беседы (решаемой проблемы).^{[источник не указан 1206 дней][уточнить]}

• Земля не может быть плоской; в противном случае мы бы обнаружили, что люди падают с края. Пример утверждает, что отрицание предпосылки привело бы к нелепому выводу вопреки свидетельству наших чувств.
• Нет наименьшего положительного рационального числа, потому что если бы оно было, то его можно было бы разделить на два, чтобы получить меньшее. Это математическое доказательство от противоречия, в котором утверждается, что отрицание предпосылки приведет к логическому противоречию (существует «наименьшее» число, и все же есть число меньше его).
• В 2011 году власти Австрии разрешили пастафарианину Нико Альму сфотографироваться на водительское удостоверение с дуршлагом на голове как религиозным головным убором. Нико Альм подал соответствующее заявление три года назад, тем самым используя аргумент reductio ad absurdum (сведение к абсурду) против разрешения мусульманам фотографироваться на документы в хиджабах. Так как фотографии с головными уборами разрешены в Австрии только из религиозных побуждений, он обосновал свой поступок принадлежностью к пастафарианству^[10]. «Моя главная цель — заставить людей задуматься над адекватностью системы», — заявил он^[11].