Введение

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

Метаматематика

О метаматематике Q см. , , , и . Предназначенная интерпретация Q – это натуральные числа и их обычная арифметика, в которой сложение и умножение имеют свое обычное значение, тождество – это равенство, а 0 – натуральное число ноль. Любая модель (структура), удовлетворяющая всем аксиомам 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 интерпретируется во фрагменте аксиоматической теории множеств Цермело, состоящем из экстенсиональности, существования пустого множества и аксиомы присоединения. Эта теория S' в и ST в . См. общую теорию множеств для получения более подробной информации. Q – это конечно аксиоматизированная теория первого порядка, которая значительно слабее арифметики Пеано (PA), и чьи аксиомы содержат только один экзистенциальный квантор. Однако, как и PA, она неполна и неполна в смысле теорем о неполноте Гёделя и по существу неразрешима. выведены аксиомы Q (1)–(7) выше, отметив, какие аксиомы PA необходимы для доказательства того, что каждая вычислимая функция представима в PA. Единственное использование этой доказательством аксиомы индукции PA – доказать утверждение, которое является аксиомой (3) выше, и, таким образом, все вычислимые функции представимы в Q. Вывод второй теоремы о неполноте Гёделя также имеет значение для Q: никакое последовательное рекурсивно аксиоматизированное расширение Q не может доказать свою собственную последовательность, даже если мы дополнительно ограничим числа Гёделя доказательств до определяемого сечения. Первая теорема о неполноте применяется только к аксиоматическим системам, определяющим арифметику, достаточную для выполнения необходимых конструкций кодирования (частью которых является нумерация Гёделя). Аксиомы Q были выбраны специально для того, чтобы они были достаточно сильными для этой цели. Таким образом, обычное доказательство теоремы о первой неполноте может быть использовано, чтобы показать, что Q неполна и неразрешима. Это указывает на то, что неполнота и неразрешимость PA не могут быть связаны с единственным аспектом PA, отличающим его от Q, а именно с аксиомой схемы индукции. Теоремы Гёделя не применимы, когда любая из семи аксиом выше отбрасывается. Эти фрагменты Q остаются неразрешимыми, но они больше не являются по существу неразрешимыми: у них есть последовательные расширения, а также неинтересные модели (то есть модели, которые не являются конечными расширениями стандартных натуральных чисел).