Читая главу про индуктивные доказательства книги "Введение в теорию автоматов, языков и вычислений", наткнулся на следующий фрагмент:
Пусть требуется доказать некое утверждение
, которое зависит от целого числа n. Существует общий подход к доказательствам такого рода. Доказательство разбивается на следующие два этапа.
1. Базис. На этом этапе мы показываем, что
верно для некоторого частного целого значения
. Обычно полагают
или
, но существуют примеры, где выбирается большее начальное значение, например, когда для всех меньших значений
утверждение
ложно.
2. Индуктивный переход. Здесь мы предполагаем, что
, где
— целое число из базиса индукции, и доказываем, что из истинности
следует истинность
, т.е. доказываем утверждение “если
, то
”. На уровне здравого смысла данное доказательство убеждает нас в том, что
на самом деле верно для всякого целого
, большего или равного базисному
. Обосновать это можно следующим образом. Предположим, что
ложно для одного или нескольких таких целых
. Тогда среди этих значений
существует наименьшее, скажем,
, причем
. Значение
не может быть равным
, так как на основании базиса индукции
истинно. Поэтому
должно быть строго больше
. Таким образом, мы знаем, что
и
истинно.
Но во второй части доказательства показано, что если
, то
влечет
. Предположим, что
. Тогда, совершая индуктивный переход, из
выводим
. Следовательно, из истинности
следует истинность
. Но мы предполагали, что справедливо отрицание доказываемого утверждения, а именно:
ложно для некоторого
. Придя к противоречию, мы тем самым доказали методом “от противного”, что
истинно для всех
.
К сожалению, в приведенных рассуждениях присутствует трудноуловимый логический изъян. Дело в том, что первый пункт нашего предположения о том, что мы можем выбрать наименьшее, для которого ложно, зависит от того, принимаем ли мы на веру справедливость принципа индукции. Это значит, что по сути единственный способ доказать существование такого есть индуктивное доказательство. Но с позиций здравого смысла приведенное нами “доказательство” вполне осмысленно, и соответствует нашему пониманию мира.Насколько я понимаю, это стандартное описание математической индукции. Но вот о каком логическом изъяне идет речь в конце фрагмента (выделено мной жирным шрифтом), я, хоть убей, не могу понять. Прошу понимающих объяснить.