Перейти к содержанию

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

Материал из Викиучебника — открытых книг для открытого мира

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

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

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

[править]

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

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

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

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

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

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

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

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

[править]

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

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

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

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

Буквами и будем обозначать произвольные предложения, а буквой — произвольные конечные множества предложений. Будем использовать запись для обозначения того факта, что предложение обосновано (доказано), исходя из предложений , или логически следует из . Отношение между множествами предложений и предложениями будем называть отношением логического следования.

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

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


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

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

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

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

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

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

Во-первых, очевидно, что эти схемы отличаются чисто графически, а значит, рассуждения по этим схемам различаются по форме. Различия такого же характера, т. е. по крайней мере по форме, имеются между предложениями и (или между предложениями и ). Даже если, находясь на классических позициях, мы считаем, что эти утверждения равносильны, то всё равно факт различия по форме является очевидным.

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

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

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

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

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

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

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

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

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

Эффективным доказательством теоремы вида называется построение объекта (или способа, позволяющего построить этот объект) и доказательство того, что этот объект действительно обладает требуемым свойством . Доказательство теоремы существования, не удовлетворяющее этим условиям, считают неэффективным.

Типичным неэффективным доказательством теоремы существования является доказательство методом от противного. Действительно, пусть требуется доказать утверждение вида — «существует объект , обладающий свойством ». Допустим, что . Путём рассуждений получаем некоторое противоречие: и . Отсюда, в силу схемы reductio ad absurdum, делаем вывод, что допущение неверно, т. е. . Далее, снимая двойное отрицание, получим и считаем доказательство завершённым. Однако такое доказательство не завершается построением хотя бы одного объекта с требуемым свойством, оно нисколько не приближает нас к построению примера такого , что , т. е. является неэффективным доказательством.

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

Неэффективные доказательства теорем существования признаются не всеми математиками. Для математиков, стоящих на традиционных классических позициях, характерным является признание без всяких ограничений закона исключённого третьего и закона снятия двойного отрицания . Они пренебрегают различиями между утверждениями и . Математики, не придерживающиеся классических взглядов (интуиционисты и конструктивисты), отрицают универсальность этих законов. Различия между утверждениями и такие математики признают весьма существенными, считая утверждение , вообще говоря, более слабым, чем . Доказательство от противного, с их точки зрения, также является неприемлемым, поскольку оно опирается на принцип снятия двойного отрицания.

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

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

[править]

Пусть прямая является касательной к окружности с центром , — точка касания. Докажем, что касательная перпендикулярна радиусу .

[править]

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


Это доказательство построено в соответствии со схемой . В качестве выступает предложение «Касательная к окружности с центром перпендикулярна радиусу , проведённому в точку касания », в качестве — «Прямая является касательной к окружности с центром ». Вспомогательное рассуждение в этом доказательстве вырождается в одно предложение — предложение . Вспомогательное рассуждение заключено в фигурные скобки.

Примеры

[править]

В математике

[править]
Доказательство иррациональности числа .

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

, откуда .

Отсюда следует, что чётно, значит, чётно и ; следовательно, делится на 4, а значит, и тоже чётны. Полученное утверждение противоречит несократимости дроби . Значит, исходное предположение было неверным, и иррациональное число.

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

[править]

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

Литература

[править]

См. также

[править]

Примечания

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