Индукции Аксиома

Утверждение о справедливости для всех хнек-рого предиката Р(х), определенного на множестве всех неотрицательных целых чисел, если выполняются следующие условия: 1) справедливо Р(0),2) для любого х, если верно Р(х), то верно и P(x+1). И. а. записывается в виде В применениях И. а. Р(х)наз. индукционным предикатом, или индукционным предложением, а х- индукционной переменной, или переменной, по к-рой производится индукция (в тех случаях, когда Р(х)содержит, кроме х, и другие параметры). При этом проверка выполненности условия 1) наз. базисом индукции, а проверка условия 2) — индукционным шагом. Допущение внутри 2) справедливости Р(х), из к-рого затем выводится P(x+i), наз. индуктивным предположением. Принципом (математической) индукции в содержательной математике наз. схема всех И. а. для всевозможных предикатов Р(х). В системе FA арифметики формальной схема индукции состоит лишь из тех И. а., к-рые соответствуют выразимым в FA предикатам (таких предикатов счетное множество). Этим обстоятельством, т. е. невозможностью выразить в FA индукцию в полном объеме, объясняется неполнота системы FA (см. Гёделя теорема о неполноте). Иногда вместо И. а. рассматривается аксиома: пусть Р(х)- некоторое свойство неотрицательных целых чисел; если для любого хиз допущения, что Р(у)верно для всех у, меньших х, следует, что верно и Р(х), то Р(х)справедливо для всех х, т. е. Эта аксиома носит название полной, или возвратной, И. а. Принцип полной индукции эквивалентен принципу обычной индукции. См. также Транс финитная индукция. Лит.:[1] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957. С. К. Соболев.