Войти
В математике Арифметика Робинсона конечно аксиоматизированный фрагмент арифметики Пеано (PA) первого порядка, впервые изложенный Р. М. Робинсон в 1950 году. Обычно обозначается Q. Qпочти PA без схемы аксиом из математической индукции. Qслабее, чем PA, но имеет тот же язык, и обе теории неполны. Qважна и интересна, потому что это конечно аксиоматизированный фрагмент PA, который рекурсивно неполон и по существу неразрешим.
Основная логика в Q - это логика первого порядка с идентификатором, обозначается инфиксом '='. Индивидуумы, называемые натуральными числами, являются членами множества, называемого N с выделенным элементом 0, называемым ноль. Есть три операции над N:
Следующие аксиомы для Q - это Q1 – Q7 у Берджесса (2005: 42) (см. Также аксиомы арифметики первого порядка ). Переменные, не связанные с квантором существования, связаны неявным универсальным квантором.
Аксиомы у Робинсона (1950) - это (1) - (13) у Мендельсона (1997: 201). Первые 6 из 13 аксиом Робинсона требуются только тогда, когда, в отличие от этого, фоновая логика не включает идентичность.
Обычный строгий общий порядок на N, «меньше чем» (обозначается «<"), can be defined in terms of addition via the rule x < y ↔ ∃z (Sz + x = y). Equivalently, we get a definitional conservative extension of Q, принимая« <" as primitive and adding this rule as an eighth axiom; this system is termed "Robinson arithmetic R "в Boolos et al. (2002: раздел 16.4).
Другое расширение Q, которое мы временно называем Q +, получается, если мы берем" <" as primitive and add (instead of the last definitional axiom) the following three axioms to axioms (1)–(7) of Q:
Q+по-прежнему является консервативным расширением Q в том смысле, что любая доказываемая формула в Q + не содержит символа «<" is already provable in Q. (Только добавление первые две из трех вышеупомянутых аксиом к Q дают консервативное расширение Q, что эквивалентно тому, что Берджесс 2005: 56 называет Q * . См. также Берджесс 2005: 230 fn. 24, но обратите внимание, что вторая из трех вышеупомянутых аксиом не может быть выведена из «чистого дефиниционного расширения» Q, полученного путем добавления только аксиомы x < y ↔ ∃z (Sz + x = y).)
Среди аксиомы (1) - (7) из Q, аксиома (3) требует внутреннего экзистенциального квантора. Шоенфилд (1967: 22) дает аксиоматизацию, которая имеет только (неявные) внешние универсальные кванторы, обходясь без аксиомы (3) из Q, но добавление трех вышеупомянутых аксиом с < as primitive. That is, Shoenfield's system is Q + минус аксиома (3) и строго слабее, чем Q +, поскольку аксиома (3) не зависит от другой аксиомы (например, порядковые числа меньше 
По метаматематике Q см. Boolos et al. (2002: chpt. 16), Tarski, Мостовски и Робинсон (1953), Смоллян (1991), Мендельсон (1997: 201–03) и Берджесс (2005: §§1.5a, 2.2). Предполагаемая интерпретация из Q - это натуральные числа и их обычная арифметика, в которых сложение и умножение имеют свое обычное значение, тождество - равенство, Sx = x + 1, а 0 - натуральное число ноль.
Любая модель (структура), которая удовлетворяет всем аксиомам Q, кроме, возможно, аксиомы (3), имеет уникальную подмодель («стандартная часть»), изоморфная стандартным натуральным числам (N, +, ·, S, 0). (Аксиома (3) может не выполняться; например, многочлены с неотрицательным целым числом коэффициенты образуют модель, которая удовлетворяет всем аксиомам, кроме (3).)
Q, как и арифметика Пеано, имеет нестандартные модели всех бесконечных автомобилей dinalities. Однако, в отличие от арифметики Пеано, теорема Тенненбаума не применима к Q, и у нее есть вычислимые нестандартные модели. Например, существует вычислимая модель Q, состоящая из многочленов с целыми коэффициентами с положительным старшим коэффициентом плюс нулевой многочлен с их обычной арифметикой.
Примечательной характеристикой Q является отсутствие схемы аксиом индукции. Следовательно, в Q часто можно доказать каждый конкретный случай факта о натуральных числах, но не соответствующую общую теорему. Например, 5 + 7 = 7 + 5 доказуемо в Q, но общее утверждение x + y = y + x - нет. Точно так же нельзя доказать, что Sx ≠ x (Burgess 2005: 56). Модель 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 (Boolos et al, 2002, раздел 16.4).
Qинтерпретируется во фрагменте аксиоматической теории множеств Цермело , состоящей из экстенсиональности, существования пустого множества и аксиома присоединения. Эта теория S 'у Тарского и др. (1953: 34) и ST в Берджессе (2005: 90–91; 223). Подробнее см. общая теория множеств.
Qинтересен тем, что это конечно аксиоматизированная теория первого порядка, которая значительно слабее, чем арифметика Пеано (PA), и чьи аксиомы содержат только один экзистенциальный квантор, но, как и PA, является неполным и неполным в смысле теорем Гёделя о неполноте и по существу неразрешимым. Робинсон (1950) вывел аксиомы Q (1) - (7) выше, отметив, какие аксиомы PA необходимы для доказательства (Mendelson 1997: Th. 3.24), что каждая вычислимая функция представима в PA. Единственное использование в этом доказательстве схемы аксиом PA индукции - это доказать утверждение, которое является аксиомой (3) выше, и, таким образом, все вычислимые функции представимы в Q (Mendelson 1997: Th. 3.33, Rautenberg 2010: 246). Заключение второй теоремы Гёделя о неполноте также справедливо для Q : никакое последовательное рекурсивно аксиоматизированное расширение Q не может доказать свою непротиворечивость, даже если мы дополнительно ограничим гёделевское количество доказательств определимым разрезом (Безборуа и Шепердсон, 1976; Пудлак, 1985; Гайек, Пудлак, 1993: 387).
Первая теорема о неполноте применима только к аксиоматическим системам, определяющим арифметические действия, достаточные для выполнения необходимых конструкций кодирования (частью которых нумерация Гёделя является частью). Аксиомы Q были выбраны специально для того, чтобы убедиться, что они достаточно сильны для этой цели. Таким образом, обычное доказательство первой теоремы о неполноте можно использовать, чтобы показать, что Q является неполным и неразрешимым. Это указывает на то, что неполнота и неразрешимость PA не может быть объяснена единственным аспектом PA, отличающим его от Q, а именно схемой аксиомы индукции.
теоремы Гёделя. не выполняется, когда отбрасывается одна из семи аксиом выше. Эти фрагменты Q остаются неразрешимыми, но они больше не являются неразрешимыми: у них есть согласованные разрешимые расширения, а также неинтересные модели (то есть модели, которые не являются конечными расширениями стандартных натуральных чисел).
