Комментарий. 1) Итак, слова «предположим противное» и «пришли к противоречию» сами по себе не являются магическим заклинанием. Распространенная ошибка – вместо требуемого утверждения доказать обратное ему. 2) Само утверждение про архипелаг верно, но доказывается сложнее, чем обратное.
Задача 7.6*. Конечно или бесконечно множество простых чисел?
Обсуждение. Не правда ли, вопрос естественный? Недаром его еще древние греки поставили. И он кажется очень сложным, не так ли? Во всяком случае, конечно ли множество пар простых чисел-близнецов (т. е. отличающихся друг от друга на 2), неизвестно до сих пор. Как не найдено и никакой формулы, позволяющей бесконечно вычислять одно простое число за другим. А некоторые простые по формулировке вопросы теории чисел решены весьма сложными современными методами (например, великая теорема Ферма или тернарная проблема Гольдбаха). Но вот вопрос о бесконечности множества простых чисел древние греки смогли не только поставить, но и решить. Приведем удивительное по красоте и простоте доказательство от противного, восходящее к «Началам» Евклида.
Решение. Пусть множество простых чисел конечно. Тогда можно выписать все простые числа: p>1, p>2, p>3…, p>n. Произведение всех этих чисел делится на каждое из них. А если его немножко «испортить», прибавив 1, то полученное число: p>1p>2p>3… p>n+ 1 не будет делиться ни на одно из простых чисел p>1, p>2, p>3…, p>n. Можно ли это число разложить на простые множители? Если можно, то среди этих простых множителей нет известных нам чисел p>1, p>2, p>3…, p>n(то есть мы выписали не все простые числа!). А если нельзя, то это число само простое, причем большее всех выписанных нами чисел. В любом случае выписать все простые числа не удалось. Значит, их множество бесконечно.
Комментарий. Является ли приведенное доказательство доказательством от противного? Если да, то требовалось бы доказать, что из А следует Б. А мы вместо этого доказывали бы, что из «не Б» следует «не А». Но где же условие А? В задаче вообще ничего не дано!
Условие А появится, если переформулировать задачу так: «Пусть дано множество всех простых чисел. Доказать, что оно бесконечно». Предположив, что множество простых чисел конечно, мы убедились, что рассмотрели не все простые числа.
Метод от противного оказался эффективен, потому что помог от бесконечного количества, с которым непонятно что делать, перейти к конечному, которое можно перечислить. А затем придумать, как по любому конечному набору простых чисел указать еще одно простое число. Теперь, когда решение придумано, его можно изложить и без характерных для метода от противного слов: возьмем произвольный набор простых чисел, к ним можно добавить еще одно, затем еще одно и т. д. Так можно делать сколько угодно раз, поэтому простых чисел бесконечно много. Еще раз убеждаемся, что сила метода от противного не в магических заклинаниях: он и без них работает!
