Математическая индукция

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

1 + 3 + 5 + ... + (2n - 1) = n² (1)

При n = 1 эта формула даёт 1 = 1². Чтобы доказать правильность формулы при любом n, допускают, что её уже удалось доказать для некоторого определённого числа N, то есть предполагают, что

1 + 3 + 5 + ... + (2N - 1) = N². (2)

Далее, опираясь на сделанное допущение, пытаются доказать правильность формулы (1) для числа на единицу большего, то есть для n = N + 1. В данном случае достаточно присоединить к сумме в левой части равенства (2) ещё одно слагаемое: (2N + 1); тогда и правая часть равенства должна увеличиться на (2N +1) и, следовательно,

1 + 3 + 5 + ... + (2N — 1) + (2N + 1) = N² + (2N + 1) = (N + 1)².

Но тот же результат получится, если в формуле (1) заменить n наN + 1.

Итак, из справедливости формулы (1) при n = N вытекает (каково бы ни было N) её правильность и при n = N + 1. Но при n = 1 формула (1) верна, следовательно, она верна также и при n = 2 = 1 + 1, 3 = 2 + 1, 4 = 3 + 1, 5 = 4 + 1 и так далее. Так как последовательным прибавлением единицы можно получить (начиная с единицы) любое натуральное число, то формула (1) действительно верна при любом натуральном числе n. Как ни очевидна заключительная часть приведённого рассуждения, она опирается на некоторую аксиому, не сводимую только к общим законам логики, но выражающую одно из основных свойств натуральных чисел. Общая формулировка этой аксиомы такова.

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

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

Принцип М. и., сформулированный выше, служит, как было показано, для доказательства математических теорем. Помимо этого, в математике употребляются ещё так называемые индуктивные определения. Таково, например, следующее определение членов u_n геометрической прогрессии с первым членом а и знаменателем q:

1)u₁ = a,

2) u_n+1 = u_nq.

Условия 1) и 2) однозначно определяют члены прогрессии u_n для всех натуральных чиселn. Доказательство того, что это действительно так, может быть основано на принципе М. и.; в данном случае можно, однако, непосредственно получить выражение u_n через n:

u_n = aq^n-1.

Принцип М. и. можно заменить равносильными ему предложениями, например таким: если подмножество М множества всех натуральных чисел N содержит 1 и вместе с любым своим элементом m содержит и m+ 1, то М = N.

МАТЕМАТИЧЕСКАЯ индукция - общий способ математического доказательства или определения некоторого свойства А для всех натуральных n, основанный на заключении от n к n+1. Математическая индукция состоит из двух этапов: а) установление А для некоторого начального n0; б) обоснование перехода от n к n+1.

МАТЕМАТИЧЕСКАЯ индукция, способ доказательства или определения некоторого свойства A для всех n случаев, основанный на переходе заключения о наличии свойства A от n к n+1. Математическая индукция состоит из двух этапов: установление A для некоторого начального n и обоснование перехода от n к n+1.

mathematical induction

math(ematical) induction, induction

МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ, метод, доказывающий, что математическое утверждение верно для любого положительного целого числа п, если выполняются два условия: 1) оно верно для основной величины, например, 1, и 2) если оно верно для значения k, то верно и для k+1. Если условия (1) и (2) выполняются, тогда это утверждение верно для любого положительного целого числа п. Формула для сумм первых натуральных чисел - результат, который можно доказать только при помощи математической индукции. Такая методика убедительно доказывает, что результат верен для бесконечного множества значений.

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

полная математическая индукция (наз. в математике часто просто полной индукцией; в этом случае это понятие следует отличать от рассматриваемого в нематематич. формальной логике понятия полной индукции), – прием доказательства общих предложений в математике и др. дедуктивных науках; особое значение имеет в связи с рассмотрением б е с к о н е ч н ы х д и с к р е т н ы х п р о ц е с с о в. Известно много различных форм М. и., но чаще всего этот термин применяют к следующему приему: доказывается, что (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

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

Для возвратной индукции также существуют разновидности, аналогичные усеченной форме М. и. В одной из таких форм принцип М. и. впервые появился в работе Паскаля "Об арифметич. треугольнике" (В. 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.

математи́ческая инду́кция

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

* * *

МАТЕМАТИ́ЧЕСКАЯ ИНДУ́КЦИЯ, общий способ математического доказательства или определения некоторого свойства А для всех натуральных n, основанный на заключении от n к n+1. Математическая индукция состоит из двух этапов:

а) установление А для некоторого начального n₀;

б) обоснование перехода от n к n+1.

метод доказательства математич. утверждений, основанный на принципе математической индукции: утверждение (х), зависящее от натурального параметра х, считается доказанным, если доказано А(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.

С. И. Адян.

math(ematical) induction, induction

* * *

mathematical induction

induzione matematica

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