Примитивно-рекурсивная арифметика

Примитивно-рекурсивная арифметика (ПРА) — формальная аксиоматическая теория в математической логике, представляющая собой фрагмент арифметики первого порядка, в котором разрешено использовать только примитивно-рекурсивные функции. ПРА была предложена норвежским математиком Торальфом Сколемом в 1923 году как попытка построить арифметику без использования кванторов (∃, ∀), что делает её более слабой, чем арифметика Пеано (PA), но достаточной для формализации значительной части обычной математики, включая доказательства теорем о непротиворечивости. В отличие от PA, ПРА не содержит аксиомы индукции для произвольных формул, а вместо этого использует схему рекурсии, определяющую функции.

История

Идея примитивно-рекурсивной арифметики возникла в контексте исследований оснований математики в начале XX века. Торальф Сколем, работая над проблемой разрешимости арифметики, в 1923 году опубликовал работу «Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnungsbereich» (Обоснование элементарной арифметики рекурсивным методом без использования кажущихся переменных с бесконечной областью). В ней он предложил систему, в которой все функции определяются рекурсивно, а аксиомы формулируются без кванторов.

В 1930-е годы концепция была развита Куртом Гёделем в его работе о неполноте. Гёдель использовал примитивно-рекурсивные функции для кодирования синтаксиса формальных систем (гёделева нумерация), что стало ключевым инструментом для доказательства теорем о неполноте. Однако сам термин «примитивно-рекурсивная арифметика» и её аксиоматизация как отдельной теории были формализованы позже, в частности, в работах Стивена Клини и Хаскелла Карри.

В середине XX века ПРА привлекла внимание в связи с программой Гильберта по обоснованию математики. ПРА рассматривалась как минимальная теория, достаточная для формализации финитистских (конечных) рассуждений, поскольку она не использует неограниченные кванторы и опирается только на явно заданные рекурсивные определения.

Аксиоматика и язык

ПРА является теорией первого порядка с равенством. Её язык состоит из:

• Константа: 0 (ноль).
• Функциональные символы: символ для функции следования S (S(x) = x + 1), а также для каждой примитивно-рекурсивной функции свой функциональный символ.
• Предикат: = (равенство).

Аксиомы ПРА делятся на две группы:

1. Аксиомы равенства: рефлексивность, симметричность, транзитивность и подстановочность (замена равного на равное).
2. Собственные аксиомы:

• S(x) ≠ 0 (ноль не является последователем никакого числа).
• S(x) = S(y) → x = y (функция S инъективна).
• Схема рекурсии: для каждой примитивно-рекурсивной функции f, определённой рекурсивно, добавляется аксиома, задающая её значение. Например, для сложения: x + 0 = x; x + S(y) = S(x + y).
• Схема индукции для примитивно-рекурсивных формул: если φ(x) — примитивно-рекурсивная формула (т.е. формула, не содержащая кванторов), то из φ(0) и ∀x (φ(x) → φ(S(x))) следует ∀x φ(x). Это более слабая форма индукции, чем в PA, где индукция разрешена для любых формул первого порядка.

Важно, что в ПРА отсутствуют кванторы существования и всеобщности в обычном смысле. Вместо этого используются ограниченные кванторы (например, ∀x < t), которые могут быть выражены через примитивно-рекурсивные функции.

Примитивно-рекурсивные функции

Основой ПРА является класс примитивно-рекурсивных функций. Это функции, которые могут быть получены из базовых (нулевая функция, функция следования, функции проекции) с помощью двух операций:

• Композиция: подстановка одной функции в другую.
• Примитивная рекурсия: определение функции f(n+1) через f(n) и n.

Примеры примитивно-рекурсивных функций:

• Сложение: add(x, 0) = x; add(x, S(y)) = S(add(x, y)).
• Умножение: mul(x, 0) = 0; mul(x, S(y)) = add(mul(x, y), x).
• Возведение в степень: exp(x, 0) = 1; exp(x, S(y)) = mul(exp(x, y), x).
• Предшествование (для натуральных чисел): pred(0) = 0; pred(S(x)) = x.
• Вычитание с усечением (x ∸ y = max(x-y, 0)): x ∸ 0 = x; x ∸ S(y) = pred(x ∸ y).

Все эти функции тотально определёны на множестве натуральных чисел и вычислимы за конечное число шагов. ПРА может доказать все их основные свойства (например, коммутативность сложения), используя только индукцию по примитивно-рекурсивным формулам.

Свойства

Непротиворечивость

ПРА является непротиворечивой теорией. Это следует из того, что её можно интерпретировать в арифметике Пеано, которая считается непротиворечивой (хотя её непротиворечивость недоказуема в самой PA по второй теореме Гёделя). Более того, ПРА настолько слаба, что её непротиворечивость может быть доказана в рамках самой ПРА с помощью финитистских методов. Это делает ПРА важным инструментом для метаматематических исследований.

Выразительная сила

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

Связь с арифметикой Пеано

Арифметика Пеано (PA) строго сильнее ПРА. PA включает все аксиомы ПРА, но также содержит аксиому индукции для любых формул первого порядка, включая те, которые содержат кванторы. Это позволяет PA доказывать более сложные утверждения, например, теорему Гёделя о неполноте (в PA она доказуема, а в ПРА — нет). ПРА является собственным фрагментом PA: любая теорема ПРА является теоремой PA, но обратное неверно.

Применение

ПРА находит применение в нескольких областях:

• Теория доказательств: ПРА используется как минимальная теория для формализации финитистских рассуждений. Например, в программе Гильберта предполагалось, что непротиворечивость PA может быть доказана в ПРА, но теоремы Гёделя показали, что это невозможно. Тем не менее, ПРА служит эталоном для оценки сложности доказательств.
• Информатика: Примитивно-рекурсивные функции лежат в основе многих алгоритмов и языков программирования. ПРА даёт формальную модель для вычислений, которые гарантированно завершаются (тотальные функции). Это используется в верификации программ и в теории сложности вычислений.
• Математическая логика: ПРА является стандартным примером для изучения формальных систем, их выразительной силы и ограничений. Она часто используется в учебниках для иллюстрации концепций рекурсии, индукции и непротиворечивости.

Критика и ограничения

Основной недостаток ПРА — её ограниченная выразительная сила. Она не может справиться с функциями, растущими быстрее примитивно-рекурсивных (например, функция Аккермана). Кроме того, отсутствие неограниченных кванторов делает невозможным формулировку многих важных утверждений, таких как «для любого x существует y, такое что...» (например, существование простых чисел-близнецов). Это ограничивает её применение в современной теории чисел и анализе.

Некоторые математики критикуют ПРА за то, что она не отражает интуитивного понятия вычислимости, поскольку класс примитивно-рекурсивных функций не включает все вычислимые функции (например, функцию, которая останавливается на всех входах, но не является примитивно-рекурсивной). Однако для целей формализации элементарной арифметики это ограничение не является критическим.

Источники

• Сколем, Т. (1923). «Begründung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Veränderlichen mit unendlichem Ausdehnungsbereich».
• Гёдель, К. (1931). «Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I».
• Клини, С. К. (1952). «Introduction to Metamathematics».
• Мендельсон, Э. (2010). «Введение в математическую логику».
• Такеути, Г. (1987). «Proof Theory».