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

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