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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{\mathcal {\neg {\neg {A}}}}\Rightarrow {\mathcal {A}}.

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

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

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

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

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

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

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

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

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

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

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

Пусть прямая p {\displaystyle p} является касательной к окружности с центром O {\displaystyle O} , A {\displaystyle A} — точка касания. Докажем, что касательная p {\displaystyle p} перпендикулярна радиусу O A {\displaystyle OA} .

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

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

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

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

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

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

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

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

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

↑ ¹ ² Косвенное доказательство//Философия: Энциклопедический словарь. — М.: Гардарики. Под редакцией А. А. Ивина. 2004.
↑ Доказательство от противного//Философия: Энциклопедический словарь. — М.: Гардарики. Под редакцией А. А. Ивина. 2004.
↑ ¹ ² Доказательство от противного // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров. — 3-е изд. — М. : Советская энциклопедия, 1969—1978.
↑ Тимофеева И. Л. Некоторые замечания о методе доказательства от противного //Математика в школе — 1994, № 3. С. 36-38.

Тимофеева И. Л. Математическая логика. Курс лекций: Учеб. пособие для студентов вузов / Ответств. ред. Н. В. Валуева. — 2-е изд., перераб. — М. : КДУ, 2007. — 304 с. — 1000 экз. — ББК 22.12я73. — УДК 510.6(075.8)^(G). — ISBN 978-5-98227-307-9.
Тимофеева И. Л. Вводный курс математики: учебное пособие для студентов учреждений высш. пед. проф. образования / И. Л. Тимофеева, И. Е. Сергеева, Е. В. Лукьянова ; под ред. В. Л. Матросова. — М. : Издательский центр «Академия», 2011. — 240 с. — 1000 экз. — ББК 22.1я73. — УДК 51 (075.8)^(G). — ISBN 978-5-7695-7960-8.
Клини С. К. Введение в метаматематику. Пер. с англ. / под ред. В. А. Успенского. — М. : Издательство иностранной литературы, 1957. — 528 с.

[кд-1] ¹ ² Косвенное доказательство//Философия: Энциклопедический словарь. — М.: Гардарики. Под редакцией А. А. Ивина. 2004.

[фэс-2] Доказательство от противного//Философия: Энциклопедический словарь. — М.: Гардарики. Под редакцией А. А. Ивина. 2004.

[бсэ-3] ¹ ² Доказательство от противного // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров. — 3-е изд. — М. : Советская энциклопедия, 1969—1978.

[док-4] Тимофеева И. Л. Некоторые замечания о методе доказательства от противного //Математика в школе — 1994, № 3. С. 36-38.

[1]

[2]

[3]

[4]

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

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

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

Рассмотрим доказательство, в котором используется метод доказательства от противного

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

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

См. также

Примечания

Литература

Категории