Доказательство от противного
Доказательство «от противного» (лат. contradictio in contrarium), или апагогическое косвенное доказательство[1], — вид доказательства, при котором «доказывание» некоторого суждения (тезиса доказательства) осуществляется через опровержение отрицания этого суждения — антитезиса[2]. Этот способ доказательства основывается на истинности закона двойного отрицания в классической логике.
Этот способ очень важен для математики, где существует много суждений, которые не могут быть доказаны по-другому[3].
Схема доказательства
Схемой доказательства от противного называют схему:
Она формализует метод доказательства от противного.
Доказательство утверждения [math]\displaystyle{ \mathcal A }[/math] проводится следующим образом. Сначала принимают предположение, что утверждение [math]\displaystyle{ \mathcal A }[/math] неверно, а затем доказывают, что при таком предположении было бы верно некоторое утверждение [math]\displaystyle{ \mathcal B }[/math], которое заведомо неверно.
Из определения импликации следует, что, если [math]\displaystyle{ \mathcal B }[/math] ложно, то формула [math]\displaystyle{ \mathcal {\neg A \Rightarrow B} }[/math] истинна тогда и только тогда, когда [math]\displaystyle{ \mathcal{\neg A} }[/math] ложно, следовательно утверждение [math]\displaystyle{ \mathcal A }[/math] истинно.
Полученное противоречие показывает, что исходное предположение было неверным, и поэтому верно утверждение [math]\displaystyle{ \mathcal{\neg\neg A} }[/math], которое по закону двойного отрицания равносильно утверждению [math]\displaystyle{ \mathcal A }[/math].
В интуиционистской логике доказательство от противного не принимается, так же как не действует закон исключённого третьего[1].
Замечание. Данная схема похожа на другую — на схему доказательства приведением к нелепости. В связи с этим их часто путают. Однако несмотря на некоторое сходство, они имеют разную форму. Причём различаются они не только по форме, но и по существу, и различие это носит принципиальный характер.
Сопоставление методов доказательства от противного и приведением к нелепости
Идея необходимости различать эти методы в преподавании математики принадлежит Феликсу Александровичу Кабакову (1927–2008), который проводил эту идею в жизнь на протяжении сорока лет работы на математическом факультете МПГУ.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Перейдём к сопоставлению соответствующих методов доказательств.
Метод доказательства от противного принято считать известным методом доказательства, однако часто термин «доказательство от противного» используется в разных смыслах и применительно к разным методам доказательства. Чаще всего метод доказательства от противного путают с методом доказательства приведением к нелепости.
Буквами [math]\displaystyle{ \mathcal {A} }[/math] и [math]\displaystyle{ \mathcal {B} }[/math] будем обозначать произвольные предложения, а буквой [math]\displaystyle{ \text{Г} }[/math] — произвольные конечные множества предложений. Будем использовать запись [math]\displaystyle{ \text{Г} \Rightarrow \mathcal {A} }[/math] для обозначения того факта, что предложение [math]\displaystyle{ \mathcal {A} }[/math] обосновано (доказано), исходя из предложений [math]\displaystyle{ \text{Г} }[/math], или [math]\displaystyle{ \mathcal {A} }[/math] логически следует из [math]\displaystyle{ \text{Г} }[/math]. Отношение [math]\displaystyle{ \Rightarrow }[/math] между множествами предложений и предложениями будем называть отношением логического следования.
Метод доказательства от противного заключается в следующем. Пусть требуется доказать предложение [math]\displaystyle{ \mathcal {A} }[/math], исходя из некоторых предложений [math]\displaystyle{ \text{Г} }[/math] (это могут быть ранее доказанные теоремы, аксиомы или допущения). Допускаем, что [math]\displaystyle{ \mathcal {A} }[/math] неверно, т. е. допускаем [math]\displaystyle{ \mathcal {\neg A} }[/math], и путём рассуждений, исходя из [math]\displaystyle{ \text{Г} }[/math] и [math]\displaystyle{ \mathcal {\neg A} }[/math], выводим противоречие, т. е. предложение [math]\displaystyle{ \mathcal {B} }[/math] и его отрицание [math]\displaystyle{ \mathcal {\neg B} }[/math]. После этого мы заключаем, что допущение неверно, а значит, верно предложение [math]\displaystyle{ \mathcal {A} }[/math]. Наше рассуждение можно описать с помощью следующей неформальной схемы рассуждений:
Именно эту схему следует называть схемой доказательства от противного.
Ситуация меняется, когда нужно опровергнуть предложение [math]\displaystyle{ \mathcal {A} }[/math], другими словами, когда предложение, которое требуется доказать, имеет вид [math]\displaystyle{ \mathcal {\neg A} }[/math] (не [math]\displaystyle{ \mathcal {A} }[/math]), т. е. является отрицательным предложением.
Например, такой вид имеет предложение: «Не существует рационального числа, квадрат которого равен 2». Доказывается оно выведением противоречия из допущения, что существует рациональное число, квадрат которого равен 2.
Итак, для того чтобы доказать отрицательное утверждение [math]\displaystyle{ \mathcal {\neg A} }[/math], допускаем, что имеет место [math]\displaystyle{ \mathcal {A} }[/math], и выводим из этого некоторое противоречие: [math]\displaystyle{ \mathcal {B} }[/math] и [math]\displaystyle{ \mathcal {\neg B} }[/math]. Неформальная схема, описывающая такой ход рассуждений, выглядит так:
Эту неформальную схему рассуждений принято называть схемой доказательства приведением к нелепости или приведением к абсурду (от лат. reductio ad absurdum).
К сожалению, обычно в практике преподавания не различают эти две схемы, два способа доказательства, чаще всего называя и тот и другой доказательством от противного.
Остановимся на причинах того, почему всё же следует различать эти схемы.
Во-первых, очевидно, что эти схемы отличаются чисто графически, а значит, рассуждения по этим схемам различаются по форме. Различия такого же характера, т. е. по крайней мере по форме, имеются между предложениями [math]\displaystyle{ \mathcal {A} }[/math] и [math]\displaystyle{ \mathcal {\neg {\neg A}} }[/math] (или между предложениями [math]\displaystyle{ \mathcal {A \rightarrow B} }[/math] и [math]\displaystyle{ \mathcal {\neg A} \vee \mathcal B }[/math]). Даже если, находясь на классических позициях, мы считаем, что эти утверждения равносильны, то всё равно факт различия по форме является очевидным.
Однако такое различие может кому-то показаться недостаточным, неубедительным для того, чтобы затевать весь этот разговор. Естественно, возникают вопросы: не равносильны ли эти схемы; в чём выражается различие между ними в практике математических доказательств; это различие лишь по форме или также по существу?
Ответить на первый вопрос: «Равносильны ли схемы contradictio in contrarium и reductio ad absurdum?» можно на неформальном уровне, не переходя на путь построения формальной логической системы. Связь между данными схемами устанавливается следующим утверждением.
❗УТВЕРЖДЕНИЕ. Схема доказательства от противного
равносильна совокупности двух систем:
- доказательства приведением к нелепости
[math]\displaystyle{ \dfrac{\text {Г}, \mathcal {A} \Rightarrow \mathcal {B} \text{ и Г}, \mathcal {A} \Rightarrow \mathcal {\neg B}}{\text{Г} \Rightarrow \mathcal {\neg A}} }[/math]
- и снятия двойного отрицания
[math]\displaystyle{ \mathcal{\neg {\neg {A}}} \Rightarrow \mathcal {A}. }[/math]
Доказательство этого утверждения можно найти в книге [4].
Доказывая методом от противного, мы используем более сильные логические средства, чем когда доказываем приведением к нелепости. Это вызвано тем, что доказательство от противного существенно опирается на правило снятия двойного отрицания, а доказательство приведением к нелепости — нет. Именно благодаря этому обстоятельству различие между схемами contradictio in contrarium и reductio ad absurdum — это различие не только по форме, но и по существу. Более того, это различие тесно связано с некоторыми проблемами оснований математики.
Дело в том, что такие логические законы, как закон исключённого третьего [math]\displaystyle{ \mathcal {A \vee \neg A} }[/math], закон снятия двойного отрицания [math]\displaystyle{ \mathcal {\neg \neg A\supset A} }[/math], схема
доказательства от противного, приводят к неэффективным конструкциям и доказательствам в математике. В первую очередь это относится к доказательствам так называемых теорем существования, т. е. теорем вида: «Существует [math]\displaystyle{ x }[/math] такой, что [math]\displaystyle{ \mathcal{P}\left(x\right) }[/math]»: [math]\displaystyle{ \left(\exist {x}\right) \mathcal{P}\left(x\right) }[/math], где [math]\displaystyle{ \mathcal{P}\left(x\right) }[/math] — некоторое свойство [math]\displaystyle{ \mathcal P }[/math], которое выполняется для [math]\displaystyle{ x }[/math], причём [math]\displaystyle{ x }[/math] пробегает некоторое множество известных объектов (чисел, формул, множеств формул, и т. п.).
Эффективным доказательством теоремы вида [math]\displaystyle{ \left(\exist {x}\right) \mathcal{P}\left(x\right) }[/math] называется построение объекта [math]\displaystyle{ x }[/math] (или способа, позволяющего построить этот объект) и доказательство того, что этот объект действительно обладает требуемым свойством [math]\displaystyle{ \mathcal P }[/math]. Доказательство теоремы существования, не удовлетворяющее этим условиям, считают неэффективным.
Типичным неэффективным доказательством теоремы существования является доказательство методом от противного. Действительно, пусть требуется доказать утверждение вида [math]\displaystyle{ \left(\exist {x}\right) \mathcal{P}\left(x\right) }[/math] — «существует объект [math]\displaystyle{ x }[/math], обладающий свойством [math]\displaystyle{ \mathcal P }[/math]». Допустим, что [math]\displaystyle{ \neg{\left(\exist {x}\right) \mathcal{P}\left(x\right)} }[/math]. Путём рассуждений получаем некоторое противоречие: [math]\displaystyle{ \mathcal B }[/math] и [math]\displaystyle{ \mathcal {\neg B} }[/math]. Отсюда, в силу схемы reductio ad absurdum, делаем вывод, что допущение неверно, т. е. [math]\displaystyle{ \neg{\neg{\left(\exist {x}\right) \mathcal{P}\left(x\right)}} }[/math]. Далее, снимая двойное отрицание, получим [math]\displaystyle{ \left(\exist {x}\right) \mathcal{P}\left(x\right) }[/math] и считаем доказательство завершённым. Однако такое доказательство не завершается построением хотя бы одного объекта с требуемым свойством, оно нисколько не приближает нас к построению примера такого [math]\displaystyle{ x }[/math], что [math]\displaystyle{ \mathcal{P}\left(x\right) }[/math], т. е. является неэффективным доказательством.
Примерами доказательств такого вида служат доказательства теорем: теоремы об ограниченности непрерывной на отрезке функции (т. е. о существовании верней и нижней границ непрерывной на отрезке функции); теоремы о существовании наибольшего и наименьшего значений у непрерывной на отрезке функции. Традиционное доказательство этих теорем методом от противного не содержит конструкции, позволяющей построить объект, о существовании которого идёт речь в теореме.
Неэффективные доказательства теорем существования признаются не всеми математиками. Для математиков, стоящих на традиционных классических позициях, характерным является признание без всяких ограничений закона исключённого третьего [math]\displaystyle{ \mathcal {A \vee \neg A} }[/math] и закона снятия двойного отрицания [math]\displaystyle{ \mathcal {\neg \neg A\supset A} }[/math]. Они пренебрегают различиями между утверждениями [math]\displaystyle{ \left(\exist {x}\right) \mathcal{P}\left(x\right) }[/math] и [math]\displaystyle{ \neg{\neg{\left(\exist {x}\right) \mathcal{P}\left(x\right)}} }[/math]. Математики, не придерживающиеся классических взглядов (интуиционисты и конструктивисты), отрицают универсальность этих законов. Различия между утверждениями [math]\displaystyle{ \left(\exist {x}\right) \mathcal{P}\left(x\right) }[/math] и [math]\displaystyle{ \neg{\neg{\left(\exist {x}\right) \mathcal{P}\left(x\right)}} }[/math] такие математики признают весьма существенными, считая утверждение [math]\displaystyle{ \neg{\neg{\left(\exist {x}\right) \mathcal{P}\left(x\right)}} }[/math], вообще говоря, более слабым, чем [math]\displaystyle{ \left(\exist {x}\right) \mathcal{P}\left(x\right) }[/math]. Доказательство от противного, с их точки зрения, также является неприемлемым, поскольку оно опирается на принцип снятия двойного отрицания.
Таким образом, различие между схемами contradictio in contrarium и reductio ad absurdum носит методологический характер, затрагивая проблему разного понимания утверждений о существовании в математике, а также связанные с эти другие проблемы оснований математики.
Примеры
В математике
- Доказательство иррациональности числа [math]\displaystyle{ \sqrt{2} }[/math].
Допустим противное: число [math]\displaystyle{ \sqrt{2} }[/math] рационально, то есть представляется в виде несократимой дроби [math]\displaystyle{ \frac{m}{n} }[/math], где [math]\displaystyle{ m }[/math] — целое число, а [math]\displaystyle{ n }[/math] — натуральное. Возведём предполагаемое равенство в квадрат:
- [math]\displaystyle{ \sqrt{2} = \frac{m}{n} }[/math] [math]\displaystyle{ \Rightarrow }[/math] [math]\displaystyle{ 2 = \frac{m^2}{n^2} }[/math], откуда [math]\displaystyle{ m^2 = 2 n^2 }[/math].
Отсюда следует, что [math]\displaystyle{ m^2 }[/math] чётно, значит, чётно и [math]\displaystyle{ m }[/math]; следовательно, [math]\displaystyle{ m^2 }[/math] делится на 4, а значит, [math]\displaystyle{ n^2 }[/math] и [math]\displaystyle{ n }[/math] тоже чётны. Полученное утверждение противоречит несократимости дроби [math]\displaystyle{ \frac{m}{n} }[/math]. Значит, исходное предположение было неверным, и [math]\displaystyle{ \sqrt{2} }[/math] — иррациональное число.
В повседневной жизни
Врач, разъясняя пациенту что тот не болен гриппом, может использовать такие рассуждения: «Если бы вы действительно были больны гриппом, то у вас была бы повышена температура, был заложен нос и т. д. Но всё это у вас отсутствует, значит, нет и гриппа»[3].
Литература
- Тимофеева И. Л. Математическая логика. Курс лекций : Учеб. пособие для студентов вузов. — 2-е изд., перераб. — М. : КДУ, 2007. — 304 с. — ISBN 978-5-98227-307-9.
См. также
- Приведение к абсурду (апагогия)
- Метод бесконечного спуска
Примечания
- ↑ 1,0 1,1 Косвенное доказательство//Философия: Энциклопедический словарь. — М.: Гардарики. Под редакцией А. А. Ивина. 2004.
- ↑ Доказательство от противного//Философия: Энциклопедический словарь. — М.: Гардарики. Под редакцией А. А. Ивина. 2004.
- ↑ 3,0 3,1 Доказательство от противного // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров. — 3-е изд. — М. : Советская энциклопедия, 1969—1978.
- ↑ Тимофеева И. Л. Некоторые замечания о методе доказательства от противного //Математика в школе — 1994, № 3. С. 36-38.