ПРИНЦИП ПОЛНОЙ ИНДУКЦИИ, ЕГО ЭКВИВАЛЕНТЫ И ОБОБЩЕНИЯ

Ю. М. ГАЙДУК (Харьков)

1. Вопрос о том, чем «является» принцип полной индукции: аксиомой или теоремой,— лишен определенного математического содержания, поскольку, с принятой в настоящее время точки зрения, классификация математических истин по аксиомам и теоремам возможна отнюдь не единственным способом и потому неизбежно носит, в значительной степени, условный характер. Так, при построении системы евклидовой геометрии постулат Плэйфера, пятый постулат Евклида и, скажем, предложение о равенстве 2d суммы углов треугольника — принципиально с равным правом могут претендовать на звание аксиомы, хотя в современных школьных учебниках предпочтение в этом смысле отдается (пожалуй, не совсем заслуженно) первому из этих трех эквивалентных предложений.

После этого разъяснения читатель, вероятно, не будет удивлен, если в одних изложениях теории натурального числа ему случится встретиться с принципом полной индукции как с теоремой, тогда как в других он найдет его в числе аксиом. Если в обоих случаях излагается аксиоматическая теория натурального числа, то можно не сомневаться, что вакансия аксиомы, освободившаяся в первом случае «за переходом рассматриваемого принципа на должность теоремы», окажется замещенной каким-то эквивалентным ему предложением. (Дело существенно не меняется и в том случае, если одна из сравниваемых теорий является не аксиоматической, а генетической*, «вовсе не содержащей аксиом». Роль последних принимают тогда на себя некоторые принципы логики.)

Большое место, занимаемое принципом полной Индукции в повседневном математическом обиходе, где он лежит в основе метода доказательства «от п к л-f-1» ив основе рекуррентных определений, — можно считать общеизвестным. Почти также общепризнано и высокое значение этого принципа с гносеологической точки зрения. Менее, однако, распространено знание логических- связей, существующих между принципом полной математической индукции и другими общими математическими истинами, в частности знание модификаций, эквивалентов и обобщений этого принципа.

Рассмотрению этих «связей» мы и посвящаем нашу статью.

2. Прежде чем переходить к установлению предложений, эквивалентных принципу полной математической индукции, необходимо уточнить употребляемое нами понятие эквивалентности. Не нужно думать, что эквивалентность двух математических истин (свойств, предложений) означает лх логическую равносильность в абсолютном смысле, — она означает только, что каждая из них является следствием другой в рамках рассматриваемой теории,—так что, при изменении этих последних, данные истины могут и перестать быть эквивалентными. Простейшую иллюстрацию сказанного может доставить нам хотя бы сопоставление двух уравнений:

х-Н=0 и (х² + 1).(% + 1) — 0.

Рассматривая эти уравнения в поле действительных чисел, мы вправе считать их эквивалентными, — чего мы не можем уже делать,

переходя к рассмотрению их в комплексных чисел.

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

3. Этими рамками послужит нам. система аксиом натурального ряда чисел. Мы остановимся на наиболее употребительной такой системе — системе аксиом Пеано, в которой принцип полной индукции принимается сам в качестве одной из аксиом. Вот эти аксиомы:

1° Единица (/) является натуральным числом.

2° Для каждого натурального числа п существует единственно непосредственно следующее за ним натуральное число л'(=л-|-/).

3° Не существует числа, для которого непосредственно следующее число равно 1,

4° Каждое натуральное число, отличное от Z, непосредственно следует за одним, и только одним, натуральным числом.

5° («Принцип полной индукции»). Если 1 обладает данным свойством Р, и если из допущения, что этим свойством обладает натуральное число п, следует, что им обладает и непосредственно следующее за ним натуральное число п', — то свойством Р обладают все натуральные числа*.

В этих аксиомах понятия натурального числа и непосредственного следования одного натурального числа за другим принимаются в качестве основных, неопределяемых понятий данной теории; понятия свойства и равенства (последнее — со всеми своими формальными законами) считаются известными из логики. Другие арифметические понятия могут быть определены посредством основных, а их свойства дедуктивно выведены из принятых аксиом и определений.

4. Теперь, когда предыдущими замечаниями постановка занимающего нас вопроса должным образом уточнена, мы можем перейти к нашей задаче — формулировке и доказательству д'вух основных эквивалентов принципа полной индукции. Первым из них мы рассмотрим так называемый принцип наименьшего натурального числа (ПНЧ): среди натуральных чисел, обладающих данным свойством Р, всегда существует наименьшее.

* Эта формулировка допускает различные перефразировки, сводящиеся к тому, что вместо свойства Р вводят в рассмотрение множество натуральных чисел, обладающих этим свойством, или предложение, зависящее от натурального числа, как от параметра. На этих тривиальных модификациях мы не будем останавливаться.

Для доказательства эквивалентности' этого предложения с принципом полной индукции нужно показать, что (при принятии первых четырех аксиом Пеано): 1) принцип наименьшего натур а льного числа является следствием принципа полной индукции и 2) принцип полной индукции, в свою очередь, является следствием принципа наименьшего натурального числа. Для словесного упрощения формулировок мы будем иногда называть (в приводимых ниже доказательствах) натуральные числа, обладающие свойством Р, просто Р-числами.

1) Итак, покажем сначала, что ПНЧ вытекает из ППИ (принципа полной индукции).

Заметим, что если единица является Р-числом, то заключение ПНЧ, очевидно, соблюдается (так как 1 является вообще наименьшим натуральным числом). Остается, следовательно, рассмотреть случай, когда 1 не будет P-числом. Тогда существуют натуральные числа, меньшие всех P-чисел (например, число 1!). Допустим теперь, вопреки тому, что нужно доказать, что среди P-чисел нет наименьшего. Пусть п — натуральное число, меньшее каждого P-числа. Тогда число п'(=/1-{-1) не может быть больше никакого P-числа (так как неравенство п<^Р влечет за собой n^f Р); в действительности оно будет меньше всех Р-чисел, так как равенство п' одному из P-чисел означало бы, что оно было бы наименьшим среди Р-чисел, что исключено нашим допущением. Скажем теперь, что натуральное число п обладает свойством Q, если оно меньше всех P-чисел. Проведенное рассуждение показывает тогда, что: 1) 1 обладает свойством Q, 2) натуральное число п' обладает свойством Q, если им обладает число п. Применяя ППИ, мы заключаем, что всё натуральные числа обладают свойством Q, т. е. что всякое натуральное число меньше любого P-числа. Отсюда, в частности, приходим к очевидно абсурдному выводу о том, что всякое Р-число меньше самого себя. Полученное противоречие и доказывает наше утверждение.

2) Убедимся теперь, что ППИ вытекает из ПНЧ.

Допустим (вопреки тому, что нам нужно показать) что не все натуральные числа обладают тем свойством Р, о котором идет речь в условии ППИ. Тогда среди существующих натуральных чисел, не обладающих свойством Р (т. е. обладающих свойством <не-Р>), в силу принятого ПНЧ, существует наименьшее. Пусть это будет число т. По условию (первая посылка доказываемого ППИ !) 1 обладает свойством Р, так что т^-1. Поэтому существует натуральное число '/л(»т— 1), за которым непосредственно следует т. Число 'т будет тогда обладать свойством Р, а вместе с ним этим свойством (вторая посылка доказываемого принципа!) должно обладать и число т. Мы пришли, таким образом, к противоречию*.

5. Установим теперь второй эквивалент ППИ — принцип «обратной» индукции (ПОИ). Если:

1° среда натуральных чисел, обладающих свойством Р, существуют числа, сколь угодно большие и если '.

2^е из предположения, что свойством Р обладает натуральное число п 1, можно заключить, что им должно обладать и число 'п(=п—1), за которым непосредственно следует т, то свойством Р обладают все натуральные числа.

1) Покажем, что ПОИ вытекает из ППИ (и его эквивалента ПНЧ). Действительно, рассмотрим натуральные числа, обладающие свойством Р, о котором говорится в условии ПОИ. В силу ПНЧ (следующего из ППИ) среди этих Р-чисел существует наименьшее т. Легко видеть, что т = 1: если бы т было отлично от 1, то существовало бы непосредственно предшествующее ему натуральное число 'т, которое тогда, в силу условия 2° доказываемого предложения, должно было бы обладать свойством Р, что противоречит, однако, тому, что оно меньше числа т (наименьшего Р-числа).

Итак, 1 является P-числом. Предположим теперь, что P-числом будет натуральное число п, и покажем, что в этом случае число л' также будет P-Числом. Рассуждая «от противного», допустим, что л' не будет P-числом. Введем в рассмотрение свойство R, приписав его всем натуральным числам, меньшим л', а также всем натуральным числам, отличным от Р-чисел. Свойством R, очевидно, обладает 1. Убедимся, что если этим свойством обладает некоторое натуральное число г, то им необходимо будет обладать и число г'. Действительно, если г обладает свойством R, то или г<л', или г не является Р-числом. В первом случае /<л', так что (каков бы знак ни осуществлялся в последнем соотношении!) число г' обладает свойством R. Во втором случае г' не может быть P-числом, так как иначе, в силу условия 2° доказываемого предложения, число г также было бы P-числом. Применяя ППИ, мы заключаем, что свойством R обладают все натуральные числа. В частности, свойством R обладают тогда и все P-числа, что возможно только в том случае, если все Р-числа меньше числа п'. Но среди P-чисел по условию 1° нашего предложения, есть сколь угодно большие и, в частности, большие л'. Полученное про-

• Читателю нужно отдать себе отчет в том, что в приведенном доказательстве использованы только- такие предложения, которое не зависят от доказываемого ППИ (так что «порочный круг* исключен). Аналогичное замечание относится ко второму доказательству в следующем п°.

т. е. большие любого наперед взятого натурального числа.

Противоречие опровергает наше допущение о том, что число п' не обладает свойством Р. Таким образом, число п' обладает свойством Р всякий раз, когда последним обладает число п. Так как 1, как мы уже видели, обладает свойством Р, то по ППИ мы теперь заключаем, что свойством Р будут обладать все натуральные числа, что и tтребовалось установить.

2) Для доказательства того, что ППИ, в свою очередь, вытекает из ПОИ, достаточно показать, что из последнего можно вывести эквивалентный ППИ принцип наименьшего натурального числа.

Итак, приняв ПОИ за аксиому, вопреки доказываемому, допустим, что ПНЧ не имеет места. Тогда для некоторого свойства Р среди чисел, обладающих этим свойством, не будет наименьшего. Припишем «свойство 5» каждому натуральному числу, которое больше какого-нибудь Р-числа. Тогда среди 5-чисел, очевидно, будут сколь угодно большие. С другой стороны, если п ( ф 1) — какое-нибудь S-число, то ’п также будет 5-числом. Действительно, по определению, п р, где р — некоторое P-число. Но тогда 'п^р, ^{а та}к как, вследствие предположения об отсутствии наименьшего Р-числа, (где

р* — некоторое P-число), то (по закону транзитивности) 'л>р*, и 'п будет 5-числом. Таким образом, к свойству 5 применим ПОИ; свойством 5 должны обладать поэтому все натуральные числа. В частности, свойством 5 должна обладать единица, что представляет, однако, очевидный абсурд, так как единица не может быть больше какого бы то ни было натурального числа. Полученное противоречие и доказывает утверждение.

6. Проиллюстрируем применение установленных выше принципов на нескольких характерных примерах.

Было бы излишне приводить здесь наиболее простые примеры применения ППИ к установлению тех или иных математических фактов: такие примеры должны быть известны читателю*. Ограничимся поэтому рассмотрением здесь лишь одного — не слишком тривиального примера.

Пусть требуется доказать, что выражение Т_я (х) = cos (л arc cos х) представляет собой при всяком натуральном значении п полином степени п относительно х — так называемые полиномы Чебышева, играющие важную роль в теории приближения функций).

* Достаточное количество упражнений на метод полной индукции имеется в известном «Задачнике по алгебре» В. А. Кречмара.