Апология математики (сборник статей)

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

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

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

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

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

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

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