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

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

полная математическая индукция (наз. в математике часто просто полной индукцией; в этом случае это понятие следует отличать от рассматриваемого в нематематич. формальной логике понятия полной индукции), – прием доказательства общих предложений в математике и др. дедуктивных науках; особое значение имеет в связи с рассмотрением б е с к о н е ч н ы х д и с к р е т н ы х п р о ц е с с о в. Известно много различных форм М. и., но чаще всего этот термин применяют к следующему приему: доказывается, что (1) число 0 обладает нек-рым свойством P [(1) наз. базой индукции ] и что (2), если произвольное натуральное число n обладает свойством Ρ (т.н. индуктивное п р е д п о л о ж е н и е), то и непосредственно следующее за ним (в ряду 0, 1, 2, ...) число n' также обладает этим свойством [(2) наз. и н д у к ц и о н н ы м ш а г о м ]; отсюда делается вывод, что всякое натуральное число m обладает свойством P (свойство P наз. и н д у к ц и о н н ы м). Символически этот метод часто выражается следующей схемой аксиом:

P(0)&∀n(P(n)⊃P(n'))⊃∀mP(m). (I)

Обоснование М. и. обычно усматривается в том, что из ∀n(P(n)⊃P(n')) по правилам логики сразу может быть выведено каждое из предложений

Р(0)⊃Р(1), Р(1)⊃Р(2), Р(2)⊃Р(3), ...

и далее Р(0) вместе с Р(0)⊃Р(1) позволяет получить P(l), P(1) вместе с P(1)⊃P(2) позволяет получить Р(2) и далее таким же образом может быть получено каждое из предложений Р(3), Р(4), ..., т.е. может быть доказано каждое предложение Р(n), где n – любая из цифр 0, 1, 2, ..., а истинность каждого из этих предложений означает истинность общего предложения ∀mP(m).

Имеются нек-рые др. формы М. и., сводящиеся к рассмотренной. Напр., можно начать рассмотрение натурального ряда не с 0, a c 1, и вообще с любого натурального числа k. Соответствующей формой М. и. будет:

Р(k)& ∀n (n ≥ k⊃(Р(n)⊃P(n')))⊃∀m(m≥k⊃P(m)).

Если в дополнение к тому, что доказаны предложения Р(k) и ∀n(n≥k⊃(P(n)⊃P(n')), доказаны еще все предложения P(0), P(1), ..., Р(k–1), то тем самым считается доказанными предложение ∀ mР(m). Последнюю форму М. и. наз. часто усеченной М. и. с базисом k; (или Р(k)). Ее частным случаем при k=0 служит рассмотренная выше "основная" форма М. и. Когда в качестве индукционного предположения берется Ρ (k), где k

∀n(∀k(k

В формализованной арифметике форма (II) M. и. выводится из формы (I) (с помощью нек-рых др. аксиом арифметики). Отсутствие члена Р(0) в формулировке возвратной индукции объясняется тем, что этот член выводится из ∀n(∀k(kзакон А⊃(A⊃B) ("из противоречия следует все, что угодно") ] из формулы k<0 (где "" – знак отрицания), к-рая доказывается с помощью М. и.

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

Для возвратной индукции также существуют разновидности, аналогичные усеченной форме М. и. В одной из таких форм принцип М. и. впервые появился в работе Паскаля "Об арифметич. треугольнике" (В. Pascal, Traiti du triangle arithmitique, 1665).

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

К М. и. примыкают метод определения функций посредством т.н. (п р и м и т и в н о й) р е к у р с и и, состоящий в том, что значение определяемой функции для натурального числа n' выражается этим определением через ее значение для n и ранее определенные функции. Под этот вид определений можно подвести и определения п р е д и к а т о в посредством рекурсии (ибо предикат можно рассматривать как функцию, принимающую два значения – "истина" и "ложь"). Имеются виды рекурсий и более общие, чем эти "примитивные".

К М. и. также примыкают т.н. индуктивные (или рекуррентные) определения [примером такого определения может служить определение формулы исчисления высказываний (см. Логика высказываний) ], на к-рых основан спец. вид доказательства, родственный М. и., – т.н. индукция по построению формулы (подробнее см. Определение, Рекурсивные функции и предикаты).

М. и. играет серьезную роль в совр. исследованиях по логич. основаниям математики. Обычно при рассмотрении формализованной системы арифметики схема М. и. является одним из постулатов. Помимо этого, схема М. и. неформально используется в метатеоретич. рассуждениях (см. Метатеория).

Следует заметить, что коль скоро для записи М. и. не используются предикатные п е р е м е н н ы е, постулат М. и. является не аксиомой, а с х е м о й а к с и о м (I). В этой схеме содержится бесконечный класс аксиом, соответствующих всевозможным формулам Р(n). Польский математик Ч. Рылль-Нардзевский ("Роль аксиомы математич. индукции в элементарной арифметике" – С. Ryll-Nardzewski, The role of the axiom of induction in elementary arithmetic, "Fundamenta Mathem.", 1952, t. 39) доказал, что схему аксиом (I) нельзя заменить никаким конечным числом аксиом, получающихся по этой схеме (именно, он показал, что такая замена непременно повлечет ослабление всей формальной арифметики).

В нек-рых системах формализованной арифметики схема аксиом (I) заменяется постулатами, по внешнему виду далекими от нее.

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

М. и. является разновидностью индукции в том смысле, что обоснование общего предложения ∀mP(m) посредством M. и. предполагает возможность доказательства каждого из "частных случаев" Р(0), P(1), Р(2),... Т.о., в основе М. и. лежит принцип бесконечной индукции по натуральному ряду. В математике встречается и др., отличные от М. и., виды индукции, посредством к-рых доказываются предложения вида ∀mР(m), где m – любое натуральное число; их обоснование также использует бесконечную индукцию. Примером могут быть всевозможные виды индукции по "конструктивным трансфинитным числам". Последний термин можно понимать как означающий всякий конструктивный способ полного упорядочения натурального ряда, не обязательно в порядке возрастания натуральных чисел. Формулировка каждого из этих видов индукции отличается от схемы (II) возвратной индукции лишь тем, что отношение "<" заменяется отношением порядка, соответствующего тому или иному способу полного упорядочения натурального ряда. Хотя идея этого метода по существу заимствована из теории множеств (в к-рой важную роль играет принцип "трансфинитной индукции", доказываемый на основе ее аксиом), сама формулировка индукции по конструктивным трансфинитам может быть отнесена к арифметике.

В дедуктивных науках встречаются и др. виды индукций, родственные М. и., но относящиеся не к натуральному ряду, а к др. дискретным процессам (в к-рых может быть несколько "нулей" и "ведущих операций" типа n' – не обязательно одноместных). Напр., дискретным процессом можно считать процесс развития аксиоматич. теории, состоящий в выведении все новых и новых следствий из ее аксиом. К этому процессу применим следующий принцип индукции ("индукция по длине логич. вывода"): если все аксиомы теории (они играют роль "нулей") обладают свойством Ρ и, коль скоро посылки нек-рого применения к.-л. из имеющихся в данной теории правил вывода ("ведущей операции") обладают свойством Ρ и заключение тоже обладает этим свойством, то каждая теорема этой теории обладает свойством Р. Обоснование этого принципа можно свести к М. и. Др. примеры – т.н. индукция по длине (логич.) формулы (длиной формулы наз. число входящих в нее логич. операций), к-рая может иметь, напр., вид следующей возвратной индукции: доказывается, что из принадлежности нек-рого свойства формуле (данного вида) длины n следует его принадлежность формуле длины n', откуда следует его принадлежность всем формулам (данного вида); само доказательство при этом состоит в рассмотрении всех случаев, соответствующих различным "ведущим операциям" (т.е. случаям, когда последней, n-й операцией в формуле является конъюнкция, дизъюнкция и т.д., пока не будут рассмотрены все случаи, соответствующие всем возможным в формулах данного вида операциям логики).

Отличие М. и. (равно как и других, только что упомянутых видов индукции в математике) от т.н. неполной индукции, характерной для экспериментальных и описат. наук, состоит в том, что в дедуктивных науках каждое применение индукции основывается на умозрит. доказательстве возможности доказательства каждого частного случая исследуемого общего предложения, в то время как в др. науках обоснование этих частных случаев носит опытный характер. Значение таких умозрит. доказательств для М. и. не следует переоценивать, т.к. они основаны на ряде допущений о натуральном ряде, характерных для интуиционистской и тем более для классической арифметики (см. Интуиционизм). К их числу относится, в частности, допущение об однозначной, с точностью до изоморфизма, определенности натурального ряда, ибо без этого допущения нельзя было бы утверждать, что в ряду доказываемых предложений Р(0), P(1), P(2), ... [к-рый можно считать натуральным рядом, т.к. в нем есть 1-й элемент: Р(0), и за всяким элементом Ρ (n) ожидается наступление Ρ (n') ] имеется предложение Ρ (m) для всякого натурального числа m, и потому нельзя было бы применить бесконечную индукцию, а значит, и обосновать М. и. Но само допущение об однозначности натурального ряда обосновывается посредством М. и.

Тут налицо связь с антич. парадоксом "кучи": одно зерно не образует кучи; если n зерен не могут образовать кучи, то и n+1 зерно не может образовать кучи; следовательно, никакое число зерен не может образовать кучи, а потому куч не существует, что противоречит опыту. Т.о., идея М. и. была известна, фактически, уже в древности. Широко известный др. формы того же парадокса (напр., "лысый"). В математике на протяжении ее истории парадоксы этого вида не возникали, и это связывается обычно с тем, что в ней не рассматриваются такие "расплывчатые", т.е. объемно-неопределенные, понятия, как "куча", и т.п. Не выяснено, однако, действительно ли ограничение круга наших понятий теми, к-рые встречаются в дедуктивных науках, исключает возможность возникновения парадоксов этого типа; с др. стороны, даже такое привычное понятие, как "натуральный ряд чисел", связано с достаточно серьезными логич. трудностями.

Изучение этого вопроса обнаружило, что он тесно связан с исследованием др. допущений, принятых в интуиционистской математике. В частности, в случае отказа от однозначной определенности натурального ряда и при одновременном изучении неск. н е и з о м о р ф н ы х натуральных рядов (или дискретных процессов, естественно сводящихся к таким рядам) невозможно безоговорочно пользоваться принципом М. и. и поэтому приходится отказываться от принятия М. и. в качестве одного из постулатов (см. "Infinitistic methods. Proceedings of the Symposium on foundations of mathematics", Warsz., 1961, с. 201–23).

Неоднократно предпринимались попытки ввести более общие (в к.-л. смысле) и более сильные, чем М. и., методы доказательства (и определения). Примером может служить т.н. индукция по континууму (числовому или линейному): 1) если к.-л. действит. число x обладает свойством Р и 2) если для всякого числа у, обладающего свойством Р, найдется число z, большее у и обладающее свойством Р, то каждое действит. число, большее х, обладает свойством Ρ (аналогичная формулировка для линейного континуума получается заменой слов "действит. число" на "точка прямой" и "больше" на "лежащая правее"). Аналогия такого метода доказательства обычной возвратной индукции очевидна. Однако роль таких "более общих" видов индукции неизмеримо скромнее роли М. и. для арифметики и трансфинитной индукции. В отличие от этих методов, исходящих из генетич. процесса построения натурального ряда (или класса трансфинитных чисел) в виде вполне упорядоченного множества (см. Порядка отношение), индукция по континууму не связана ни с каким эффективным способом "построения" континуума (причем перспектива эффективного вполне-упорядочения континуума представляется безнадежной).

Лит.: Maрков Α. Α., Теория алгорифмов, Тр. Матем. ин-та им. В. А. Стеклова, т. 42, М., 1954; Клини С. К., Введение в метаматематику, М., 1957, гл. 2 (§ 7), 6, 8 (имеется большая библиография); Логич. исследования. Сб. ст., М., 1959, с. 218–62; Ηовиков П. С, Элементы матем. логики, М., 1959, гл. 5; Соминский И. С., Метод М. и., 6 изд., М., 1961; Генкин Л., О М. и., пер. с англ., М., 1962; Hilbеrt D. und Bernays P., Grundlagen der Mathematik, Bd 2, В., 1939.

Философская Энциклопедия. В 5-х т. — М.: Советская энциклопедия. Под редакцией Ф. В. Константинова. 1960—1970.