Аксиоматика натуральных чисел содержание

Доказательство по индукции

Большинство предло­жений теории чисел являются утверждениями о произвольном натуральном числе; например, теорема Лагранжа говорит о том, что каждое натуральное число есть сумма не более четырех квадратов. Как же доказать, что некоторое утверждение истин­но для любого натурального числа? Конечно, некоторые утвер­ждения непосредственно вытекают из законов арифметики; та­ковы, например, алгебраические тождества типа
(n+1)² = n² +2n+ 1.
Но более интересные и более арифметические по своей природе утверждения не столь просты.
Ясно, что мы никогда не докажем общего предложения, последовательно убеждаясь в его истинности для 1, 2, 3 и так далее, ибо нельзя перебрать бесконечного числа возможностей. Установив, что утверждение верно для любого числа, меньшего миллиона или миллиона миллионов, мы не приблизимся к до­казательству того, что оно верно всегда. (Иногда, правда, бывает, что некоторые предложения теории чисел, установленные путем вычислений для большого числа частных случаев, ока­зываются верными в довольно широкой области.)
Может быть, однако, мы найдем общее доказательство того, что если наше предложение верно для каждого из чисел 1,2,..., n-1, то оно верно и для следующего натурального числа n.
Если это доказано, то из истинности нашего предложения для числа 1 следует, что оно верно для числа 2, из того, что оно верно для 1 и 2, вытекает, что оно верно для 3, и так далее до бесконечности. Это предложение будет поэтому верным для любого числа, если оно верно для числа 1.
В этом и состоит принцип доказательства по индукции, ко­торый относится к предложениям о том, что что-то верно для любого натурального числа. Чтобы применить этот принцип, необходимо доказать две вещи: во-первых, нужно доказать, что предложение верно для 1, а во-вторых, что если предложение верно для каждого из чисел 1, 2, ..., n-1, меньших n, то оно верно и для числа n. Установив эти факты, мы заключаем, что доказываемое предложение верно для любого натурального числа.
Простой пример проиллюстрирует этот принцип. Будем изу­чать отрезки ряда 1 + 3 + 5 + ... последовательных нечетных чисел. Легко заметить, что
1 = 1², 1+3=2², 1+3+5=3², 1+3+5+7=4²
и т. д.
Этим подсказывается общее утверждение: при любом нату­ральном n сумма первых n нечетных чисел равна n². Докажем это общее предложение по индукции. Оно, конечно, верно, если n равно 1. Мы должны доказать, что результат верен для лю­бого натурального числа n; в силу принципа индукции можно предполагать, что предложение уже доказано для всех нату­ральных чисел, меньших n. Пусть, и частности, нам уже из­вестно, что сумма первых n-1 нечетных чисел равна (n-1)². Сумма первых n нечетных чисел получится из нее добавлени­ем n-го нечетного числа, равного 2n-1. Таким образом, сумма первых n нечетных чисел есть
(n-1)² + 2n - 1,
что равно n². Этим требуемое утверждение доказано.
Изложение доказательства по индукции в безупречной фор­ме требует некоторого внимания. В приведенном примере дока­зывалось, что сумма первых n нечетных чисел равна n². Здесь n — любое натуральное число, и, конечно, утверждение не изме­нится, если всюду, где встречается n, употреблять какой-нибудь другой символ. Когда мы приступаем к доказательству, n есть вполне определенное число и имеется опасность употребить один и тот же символ в разных смыслах или даже высказать бессмыс­лицу типа «предложение верно при n, равном n-1». Чтобы избежать этого, нужно использовать в случае необходимости разные символы.
С общелогической точки зрения нет ничего более очевид­ного, чем законность доказательства по индукции. Тем не менее, можно спорить, является ли этот принцип по своей при­роде определением или аксиомой или это логический принцип. Но, так или иначе, ясно, что принцип индукции служит для того, чтобы расположить натуральные числа в определенном порядке: установив, что вначале идут числа 1, 2, .... n-1, мы объявляем следующим числом число n. Таким образом, этот принцип объясняет, что означают на самом деле слова «и так далее», встречающиеся при попытке перечислить вес натураль­ные числа.