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

- утверждение о справедливости для всех хнек-рого предиката Р(х), определенного на множестве всех неотрицательных целых чисел, если выполняются следующие условия. 1) справедливо Р(0),2) для любого х, если верно Р(х), то верно и P(x+1). И. А. Записывается в виде В применениях И. А. Р(х)наз. Индукционным предикатом, или индукционным предложением, а х- индукционной переменной, или переменной, по к-рой производится индукция (в тех случаях, когда Р(х)содержит, кроме х, и другие параметры). При этом проверка выполненности условия 1) наз. Базисом индукции, а проверка условия 2) - индукционным шагом. Допущение внутри 2) справедливости Р(х), из к-рого затем выводится P(x+i), наз. Индуктивным предположением. Принципом (математической) индукции в содержательной математике наз.

Схема всех И. А. Для всевозможных предикатов Р(х). В системе FA арифметики формальной схема индукции состоит лишь из тех И. А., к-рые соответствуют выразимым в FA предикатам (таких предикатов счетное множество). Этим обстоятельством, т. Е. Невозможностью выразить в FA индукцию в полном объеме, объясняется неполнота системы FA (см. Гёделя теорема о неполноте). Иногда вместо И. А. Рассматривается аксиома. Пусть Р(х)- некоторое свойство неотрицательных целых чисел. Если для любого хиз допущения, что Р(у)верно для всех у, меньших х, следует, что верно и Р(х), то Р(х)справедливо для всех х, т. Е. Эта аксиома носит название полной, или возвратной, И. А. Принцип полной индукции эквивалентен принципу обычной индукции. См. Также Транс финитная индукция.

Лит.:[1] Клини С. К., Введение в метаматематику, пер. С англ., М., 1957. С. К. Соболев..