16. Змей Горыныч и транзитивность35

Литература38

Список обозначений39

ПРЕДИСЛОВИЕ

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

(в особенности, для студентов факультетов начальных классов), школьников-старшеклассников и учителей математики.

Авторы

Москва, 2011

1. ПАРАДОКС МАТЕМАТИЧЕСКОЙ ИНДУКЦИИ

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

В простейшем случае действие метода выглядит так. Пусть имеется некоторое утверждение A(n), зависящее от натурального номера n (n = 1,2,…). Тогда если A(1) истинно и если из истинности A(n) следует истинность A(n+1), то A(n) истинно при всех натуральных n.

Итак, доказывая истинность A(n+1), мы можем опереться на недоказанную истинность A(n) – великолепная возможность, которую не предоставляют никакие другие методы. (Как мы увидим ниже, за этой возможностью скрывается довольно любопытный парадокс.)

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

(1)

Здесь формулы над чертой – так называемые посылки, истинность которых мы должны предварительно установить, формула под чертой – вывод, истинность которого обеспечивается истинностью посылок; N обозначает множество натуральных чисел.

Парадокс, однако, заключается в том, что, «применяя математическую индукцию», мы пользуемся не методом (1), а другими соображениями.

Действительно, посмотрим, как фактически проводится доказательство «по индукции».