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

§ 6. Принципы наибольшего и наименьшего числа и метод бесконечного спуска

§ 6. Принципы наибольшего и наименьшего числа и метод бесконечного спуска

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

Принцип наименьшего числа формулируется так: в любом непустом (а не только в конечном!) множестве натуральных чисел существует наименьшее число.

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

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

Принцип наибольшего числа и обе формулировки принципа наименьшего числа с успехом применяются в доказательствах. Продемонстрируем это на примерах 13–15.

Пример 13. Доказать, что любое натуральное число, большее единицы, имеет простой делитель. Рассматриваемое число делится на единицу и на само себя. Если других делителей нет, то оно простое, а значит, является искомым простым делителем. Если же есть и другие делители, то берём из этих других наименьший. Если бы он делился ещё на что-то, кроме единицы и самого себя, то это «что-то» было бы ещё меньшим делителем исходного числа, что невозможно. Пример 14. Доказать, что для любых двух натуральных чисел существует наибольший общий делитель. Поскольку мы договорились начинать натуральный ряд с единицы (а не с ноля), то все делители любого натурального числа не превосходят самого этого числа и, следовательно, образуют конечное множество. Для двух чисел множество их общих делителей (т. е. таких чисел, каждое из которых является делителем для обоих рассматриваемых чисел) тем более конечно. Найдя среди них наибольшее, получаем требуемое. Пример 15. Доказать, что среди всех равных друг другу дробей непременно найдётся несократимая дробь. Первое доказательство – со ссылкой на пример 14, а следовательно, с косвенным использованием принципа наибольшего числа. В нашем множестве дробей выберем произвольную дробь и найдём наибольший общий делитель d её числителя и знаменателя. Если d = 1, то выбранная нами дробь уже несократима. Если d ≠ 1, то сократим её числитель и знаменатель на это число d. Полученная дробь будет несократимой. Ведь если бы её можно было бы ещё сократить на какое-то число q, то произведение dq, большее числа d, было бы делителем числителя и знаменателя первоначальной дроби и d не было бы наибольшим общим делителем. Второе доказательство – с использованием принципа наименьшего числа. Рассмотрим множество натуральных чисел, к которому отнесём всякое число, являющееся знаменателем какой-нибудь из дробей нашей коллекции равных дробей. Найдём в этом множестве наименьшее число. Дробь с таким знаменателем будет несократима, потому что при любом сокращении и числитель, и знаменатель уменьшаются. Третье доказательство – с использованием второй формулировки принципа наименьшего числа. Предположим, что в нашем множестве дробей нет несократимой. Возьмём произвольную дробь из этого множества и сократим её. Полученную тоже сократим и т. д. Знаменатели этих дробей будут всё меньшими и меньшими, и возникнет бесконечная убывающая последовательность натуральных чисел, что невозможно.