Схема аксиом индукции

Схема аксиом индукции — это формальная запись принципа математической индукции в языке логики первого порядка, используемая в аксиоматических теориях, таких как арифметика Пеано. В отличие от единичной аксиомы, схема представляет собой бесконечное множество аксиом, каждая из которых соответствует конкретной формуле языка. Она служит для доказательства утверждений, касающихся всех натуральных чисел, и является фундаментальным инструментом в основаниях математики и теории доказательств.

История

Принцип математической индукции в неявной форме использовался ещё в античности, например, в работах Евклида. Однако его формализация в рамках аксиоматической теории началась в конце XIX века. В 1889 году итальянский математик Джузеппе Пеано опубликовал аксиомы для натуральных чисел, среди которых была аксиома индукции, сформулированная на естественном языке. Позднее, с развитием логики первого порядка, стало ясно, что единая аксиома, содержащая квантор по свойствам (второй порядок), невыразима в первопорядковой логике. Выходом стало введение схемы аксиом — бесконечного набора аксиом, по одной для каждой формулы, которая может быть построена в языке теории. Эта схема была впервые явно сформулирована в работах Рихарда Дедекинда и уточнена в рамках формальной арифметики Пеано (PA) в начале XX века.

Формальное определение

Схема аксиом индукции в арифметике Пеано (PA) записывается следующим образом:

Для любой формулы φ(x) языка арифметики, содержащей свободную переменную x (и, возможно, другие параметры), аксиомой является предложение:

\[ ( \varphi(0) \land \forall x \, ( \varphi(x) \to \varphi(S(x)) ) ) \to \forall x \, \varphi(x) \]

Здесь:

• 0 — константа, обозначающая ноль;
• S(x) — функция следования, обозначающая следующее за x натуральное число;
• φ(0) — результат подстановки 0 вместо x в формулу φ;
• ∀x — квантор всеобщности по натуральным числам.

Смысл схемы: если свойство, выраженное формулой φ, выполняется для нуля, и из его выполнимости для произвольного числа x следует выполнимость для следующего числа S(x), то это свойство выполняется для всех натуральных чисел.

Примеры инстанций схемы

Схема порождает бесконечно много аксиом. Например, для формулы φ(x) := (x + 0 = x) инстанция схемы будет выглядеть так:

\[ ( (0 + 0 = 0) \land \forall x \, ( (x + 0 = x) \to (S(x) + 0 = S(x)) ) ) \to \forall x \, (x + 0 = x) \]

Другой пример: для формулы φ(x) := (x \neq S(x)):

\[ ( (0 \neq S(0)) \land \forall x \, ( (x \neq S(x)) \to (S(x) \neq S(S(x))) ) ) \to \forall x \, (x \neq S(x)) \]

Отличие от аксиомы индукции второго порядка

В логике второго порядка аксиома индукции формулируется как единое предложение с квантором по свойствам:

\[ \forall P \, ( (P(0) \land \forall x \, (P(x) \to P(S(x))) ) \to \forall x \, P(x) ) \]

Здесь P — переменная, пробегающая по всем подмножествам натуральных чисел. Эта аксиома существенно сильнее схемы первого порядка, так как позволяет проводить индукцию по произвольным свойствам, включая те, которые не выразимы формулой первого порядка. Однако в логике первого порядка такая запись невозможна, поскольку кванторы по свойствам запрещены. Схема аксиом является компромиссом: она охватывает только те свойства, которые могут быть заданы формулами языка, но их число бесконечно.

Роль в арифметике Пеано

Арифметика Пеано (PA) — это теория первого порядка, аксиомами которой являются:

1. ∀x (S(x) ≠ 0) — ноль не является следующим ни для какого числа.
2. ∀x ∀y (S(x) = S(y) → x = y) — функция следования инъективна.
3. ∀x (x + 0 = x) — определение сложения с нулём.
4. ∀x ∀y (x + S(y) = S(x + y)) — определение сложения со следования.
5. ∀x (x · 0 = 0) — определение умножения на ноль.
6. ∀x ∀y (x · S(y) = (x · y) + x) — определение умножения со следования.
7. Схема аксиом индукции (для всех формул языка).

Без схемы индукции теория была бы чрезвычайно слабой: она позволяла бы доказывать только конкретные вычислительные факты, но не общие утверждения, такие как коммутативность сложения или отсутствие бесконечных убывающих цепочек. Схема индукции придаёт теории дедуктивную силу, достаточную для формализации значительной части элементарной теории чисел.

Ограничения и неполнота

Схема аксиом индукции первого порядка не позволяет охватить все свойства натуральных чисел. Согласно теоремам Гёделя о неполноте, любая непротиворечивая теория первого порядка, включающая арифметику Пеано, является неполной: существуют истинные утверждения о натуральных числах, которые не могут быть доказаны в рамках этой теории. В частности, сама схема аксиом индукции не может быть заменена конечным набором аксиом — любая попытка её конечной аксиоматизации приводит к потере выразительной силы.

Кроме того, схема индукции первого порядка не позволяет проводить индукцию по свойствам, которые не выразимы формулами языка. Например, свойство «быть стандартным натуральным числом» (в нестандартных моделях арифметики) не может быть задано никакой формулой первого порядка, и поэтому индукция по нему недоступна.

Применение в других теориях

Схема аксиом индукции используется не только в арифметике, но и в других формальных теориях, где требуется рассуждение по индукции. Например:

• Теория множеств Цермело — Френкеля (ZF): в ней существует схема аксиом индукции для ординалов (трансфинитная индукция), а также схема аксиом выделения и замещения, которые по своей структуре аналогичны схемам.
• Арифметика второго порядка: в ней схема индукции первого порядка заменяется аксиомой индукции второго порядка, что позволяет доказывать более сильные утверждения, но за счёт выхода за рамки логики первого порядка.
• Теория типов: в интуиционистских и конструктивных теориях схема индукции часто формулируется как правило вывода, а не аксиома, что ближе к её операциональному смыслу.

Интересные факты

• Схема аксиом индукции является примером того, как бесконечное множество аксиом может быть задано конечным описанием. Это возможно благодаря тому, что формулы языка строятся по рекурсивным правилам.
• В арифметике Пеано схема индукции не является независимой от остальных аксиом: существуют модели, в которых аксиомы 1–6 выполняются, а некоторые инстанции схемы — нет. Такие модели называются нестандартными и содержат «бесконечные» натуральные числа.
• В 1931 году Курт Гёдель показал, что непротиворечивость арифметики Пеано не может быть доказана средствами самой арифметики, что связано с ограничениями, накладываемыми схемой индукции.

Источники

1. Пеано, Джузеппе. «Арифметические принципы, изложенные новым методом» (1889).
2. Гёдель, Курт. «О формально неразрешимых предложениях Principia Mathematica и родственных систем» (1931).
3. Мендельсон, Эллиотт. «Введение в математическую логику» (глава 3, арифметика Пеано).
4. Клини, Стивен Коул. «Математическая логика» (глава 4, индукция и рекурсия).
5. Ершов, Юрий Леонидович; Палютин, Евгений Андреевич. «Математическая логика» (раздел о формальной арифметике).