Философская энциклопедия - математическая индукция

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

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