МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ

метод доказательства математич. утверждений, основанный на принципе математической индукции: утверждение (х), зависящее от натурального параметра х, считается доказанным, если доказано А(1) и для любого натурального пиз предположения, что верно (п), выведено, что верно также А(n+1).

Доказательство утверждения А(1) составляет первый шаг (или базис) индукции, а доказательство А(n+1)в предположении, что верно (п), наз. индукционным переходом. При этом хназ. параметром индукции, а предположение (п).при доказательстве А(n+1) наз. индуктивным предположением. Принцип М. и. является также основанием для индуктивных определений. Простейшим примером такого определения является определение свойства: "быть словом длины n в данном алфавите

Базис индукции: каждая буква алфавита (*) есть слово длины 1. Индукционный переход: если Е - слово длины п, то каждое слово Еa_i, где есть слово длины n+1. Индукция может начинаться с нулевого шага. Часто бывает так, что А(1) и А(n+1) доказываются аналогичными рассуждениями. В таких случаях удобно пользоваться следующей эквивалентной формой принципа М. и. Если для всякого пиз предположения: (х).верно при любом натуральном x<n - следует, что (х).верно также при х=п, то утверждение (х).верно при любом натуральном х. В такой форме принцип М. и. может быть применен для доказательства утверждений (х), в к-рых параметр хпробегает то пли иное множество, вполне упорядоченное по нек-рому трансфинитному типу (трансфинитная индукция). В качестве простых примеров трансфинитной индукции отметим индукцию по параметру, пробегающему множество всех слов в данном алфавите, упорядоченное лексикографически, и индукцию по построению формул в данном логико-математич. исчислении.

Иногда для доказательства нек-рого утверждения А(n) индукцией по пприходится одновременно с (п).доказывать индукцией по пряд других утверждений, без к-рых индукцию для (п).не удается провести. В формальной арифметике можно указать такие утверждения (п), для к-рых в рамках рассматриваемого исчисления индукция не может быть проведена без добавления новых вспомогательных утверждений, зависящих от п(см. [3]). В таких случаях мы имеем дело с доказательством ряда утверждений совместной математической индукцией. Все эти утверждения формально можно объединить в одну конъюнкцию, однако практически такое объединение только усложнило бы рассмотрение, т. к. при этом исчезла бы возможность неформальных осмысленных ссылок на определенные индуктивные предположения.

В нек-рых конкретных математич. исследованиях число понятий и утверждений, определяемых и доказываемых сложной совместной индукцией, исчисляется трехзначной цифрой (см. [4]). В этом случае ввиду наличия в индуктивном доказательстве большого числа перекрестных ссылок на индуктивные предположения, для содержательного (неформального) понимания любого (даже самого простого) определения или утверждения при данном достаточно большом значении параметра индукции читатель должен быть знаком с содержанием всех вводимых совместной индукцией понятий и многих свойств этих понятий для меньших значений параметра индукции. По-видимому, единственным корректным с логич. точки зрения выходом из возникающего здесь логич. круга является аксиоматич. изложение всей рассматриваемой системы понятий. Таким образом, большое число понятий, определяемых совместной индукцией, приводит к необходимости применения аксиоматического метода в индуктивном определении и доказательстве. Это - наглядный пример необходимости аксиоматич. метода для решения конкретных математич. задач, а не только вопросов, относящихся к основаниям математики.

Лит.:[1] Гильберт Д., Б е р н а й с П., Основания математики. Логические исчисления и формализация арифметики, пер. с нем., М., 1979; [2] К л и н и С. К., Введение в метаматематику, пер. с англ., М., 1957; [3] Ц и н м а н Л. Л., "Матем. сб.", 1968, т. 77, №1, с. 71-104; [4] Адян С. И., Проблема Бернсайда и тождества в группах, М., 1975.

С. И. Адян.