§ 5. Доказательства от противного - Апология математики (сборник статей) - Владимир Андреевич Успенский - RutLib.com

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

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

Пример 10. Этот пример встречается и в «Началах» Евклида, и в современных школьных учебниках. Пусть дан треугольник и два его неравных угла. Требуется доказать утверждение A: против большего угла лежит бóльшая сторона.

Делаем противоположное предположение B: сторона, лежащая в нашем треугольнике против большего угла, меньше или равна стороне, лежащей против меньшего угла. Предположение B вступает в противоречие с ранее доказанной теоремой о том, что в любом треугольнике против равных сторон лежат равные углы, а если стороны неравны, то против большей стороны лежит больший угол. Значит, предположение B неверно, а верно утверждение А. Интересно, что прямое (т. е. не «от противного») доказательство теоремы A оказывается намного более сложным.

Пример 11. Иррациональность квадратного корня из двух. Арифметическое доказательство. Обозначим этот корень буквой r и начнём рассуждать от противного. Итак, число r рационально и таково, что r² = 2. Всякое рациональное число выражается дробью. Все выражающие число r дроби равны друг другу. Среди них найдётся несократимая дробь – доказательство этого простого факта составляет предмет примера 15. Пусть эта дробь есть m/n. Следовательно,

(m/n)² = 2.

Освобождаясь от знаменателя, получаем:

m² = 2n². (1)

Мы видим, что число m2 чётно. Но квадрат любого нечётного числа всегда нечётен; значит, число m чётно, m = 2k при некотором целом k. Подставляя 2k в формулу (1) вместо m, получаем:

(2k)² = 2n² (2)

и после сокращения на 2

2k² = n². (3)

Совершенно так же, как мы убедились в чётности m, убеждаемся в чётности n. Итак, оба числа m и n чётны, и дробь m/n можно сократить на 2, а ведь мы выбрали её несократимой. Полученное противоречие доказывает, что число r не может быть рациональным, оно иррационально.

Пример 12. Доказать, что уравнение x³ + x + 1 = 0 не имеет решений в рациональных числах.

Рассуждаем от противного. Предположим, что наше уравнение имеет рациональный корень. Запишем его в виде несократимой дроби p/q. Итак, p³/q³ + p/q + 1 = 0. Умножая обе части на q³, получаем равенство p³ + pq² + q³ = 0. Замечаем, что если хотя бы одно из чисел p и q нечётно, то нечётно и выражение p³ + pq³ + q³. Но этого не может быть, потому что оно равно нолю, а ноль – число чётное. Значит, числа p и q оба чётные, но этого тоже не может быть, потому что дробь p/q несократима.

Чаще всего способом от противного доказывают, что объекта с заданными свойствами не существует. В самом деле, если требуется доказать, что что-то существует, то можно просто предъявить соответствующий объект (конечно, надо ещё доказать, что предъявлено именно то, что надо, т. е. что предъявленный объект обладает требуемыми свойствами). А как доказать, что чего-то нет? Хорошо, если это «что-то» надо искать среди конечного количества элементов, тогда можно попробовать метод перебора. А если среди бесконечного? Один из методов, применяемых в этом случае, есть так называемый метод бесконечного спуска, речь о котором пойдёт ниже, в § 6, и который можно рассматривать как частный случай метода доказательства от противного.