Арифметика Робинсона

Арифметика Робинсона обозначается Q и получается из PA заменой схемы аксиом индукции на ${\displaystyle a=0\lor \exists xa=Sx}$ (аксиома предшественника).

Q слабее PA, но имеет тот же язык, и обе теории неполны. Она играет роль минимально достаточной теории, для которой справедливы теоремы Гёделя о неполноте^[2]. Q важна и интересна, так как является конечно аксиоматизированным фрагментом PA, который рекурсивно незавершаем и по существу неразрешим.

Фоновая логика Q — это логика первого порядка с тождеством, обозначаемым инфиксом '='. Индивидуумы, называемые натуральными числами, являются членами множества N с выделенным членом 0 , называемым нулём . Над N существует три операции:

• Унарная операция, называемая преемником и обозначаемая префиксом S;
• Две бинарные операции, сложение и умножение, обозначаются инфиксными знаками + и · соответственно.

Примем следующую сигнатуру ${\displaystyle \sigma _{*}:=\langle 0;s,+,\times ,\exp ;\leqslant ,=\rangle }$.

Под арифметикой Робинсона понимают ${\displaystyle \sigma _{*}}$-теорию с равенством, определяемую следующими аксиомами:

1. ${\displaystyle \forall xs(x)\neq 0}$;
2. ${\displaystyle \forall x\forall y(s(x)=s(y)\to x=y)}$;
3. ${\displaystyle \forall xx+0=x}$;
4. ${\displaystyle \forall x\forall yx+s(y)=s(x+y)}$;
5. ${\displaystyle \forall xx\times 0=0}$;
6. ${\displaystyle \forall x\forall yx\times s(y)=x\times y+x}$;
7. ${\displaystyle \exp(0)=s(0)}$;
8. ${\displaystyle \forall x\exp(s(x))=\exp(x)+\exp(x)}$;
9. ${\displaystyle \forall x(x\leqslant 0\leftrightarrow x=0)}$;
10. ${\displaystyle \forall x\forall y(x\leqslant s(y)\leftrightarrow x\leqslant y\lor x=s(y))}$;
11. ${\displaystyle \forall x0\leqslant x}$;
12. ${\displaystyle \forall x\forall y(s(x)\leqslant y\leftrightarrow x\leqslant y\land x\neq y)}$.

Арифметика Пеано, обозначаемая PA, получается посредством добавления к RA всех ${\displaystyle \sigma _{*}}$- формул вида:

${\displaystyle \Phi (0,{\vec {y}})\land \forall x(\Phi (x,{\vec {y}})\rightarrow \Phi (s(x),{\vec {y}}))\rightarrow \forall x(\Phi (x,{\vec {y}})}$

где x не входит в ${\displaystyle {\vec {y}}}$; множество таких формул называют схемой аксиом индукции для ${\displaystyle \sigma _{*}}$.

Первые 6 из 12 аксиом Робинсона требуются только тогда, когда фоновая логика не включает тождество^[3].

Обычный строгий полный порядок на N , «меньше чем» (обозначаемый как «<»), может быть определён в терминах сложения через правило x < y ↔ ∃ z (Sz + x = y). Также получают консервативное расширение Q, принимая «<» как примитив и добавляя это правило как восьмую аксиому; эта система называется «арифметикой Робинсона RA»^[4].

Предполагаемая интерпретация Q — это натуральные числа и их обычная арифметика, в которой сложение и умножение имеют своё обычное значение, тождество — это равенство, Sx = x + 1, а 0 — это натуральное число ноль^[5].

Любая модель (структура), удовлетворяющая всем аксиомам Q , за исключением аксиомы (3), имеет уникальную подмодель («стандартную часть»), изоморфную стандартным натуральным числам (N , +, ·, S, 0) . Аксиома (3) не обязательно должна быть удовлетворена; например, многочлены с неотрицательными целыми коэффициентами образуют модель, удовлетворяющую всем аксиомам, за исключением (3).

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

Примечательной характеристикой Q является отсутствие аксиоматической схемы индукции. В Q часто можно доказать каждый конкретный случай для натуральных чисел, но не связанную с ним обобщённую теорему. Например, 5 + 7 = 7 + 5 доказуемо в Q , но общее утверждение x + y = y + x — нет. Аналогично, нельзя доказать, что Sx ≠ x . Модель Q получается путём присоединения двух различных новых элементов a и b к стандартной модели натуральных чисел и определения Sa = a , Sb = b , x + a = b и x + b = a для всех x , a + n = a и b + n = b , если n — стандартное натуральное число, x · 0 = 0 для всех x , a · n = b и b · n = a , если n — ненулевое стандартное натуральное число, x · a = a для всех x , кроме x = a , x · b = b для всех x , кроме x = b , a · a = b , и b · b = a .

Q интерпретируется во фрагменте аксиоматической теории множеств Цермело, состоящей из экстенсиональности, существования пустого множества и аксиомы присоединения.

Q — значительно слабее арифметики Пеано (PA), её аксиомы содержат только один квантор существования. Как и PA, она неполна в смысле теорем Гёделя о неполноте, и по существу неразрешима. Р. Робинсон вывел аксиомы Q (1)-(7), отметив, какие именно аксиомы PA требуются для доказательства вычислимости функции в PA. Все вычислимые функции представимы в Q, кроме утверждения аксиомы (3). Заключение второй теоремы Гёделя о неполноте справедливо и для Q: никакое непротиворечивое рекурсивно аксиоматизированное расширение Q не может доказать свою собственную непротиворечивость, даже если мы дополнительно ограничим число доказательств Гёделя определимым разрезом.

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

Теоремы Гёделя не выполняются, если отбросить любую из семи аксиом выше. Эти фрагменты Q остаются неразрешимыми, но они больше не являются по сути неразрешимыми: у них есть согласованные разрешимые расширения, а также неинтересные модели (то есть модели, которые не являются конечными расширениями стандартных натуральных чисел).