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

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

Аксиомы

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

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

Следующие аксиомы для Q - это Q1 – Q7 у Берджесса (2005: 42) (см. Также аксиомы арифметики первого порядка ). Переменные, не связанные квантором существования , связаны неявным универсальным квантором .

1. Sx ≠ 0
   • 0 не является преемником какого-либо числа.
2. ( Sx = Sy ) → x = y
   • Если преемник x идентичен преемнику y , то x и y идентичны. (1) и (2) дают минимум фактов о N (это бесконечное множество, ограниченное числом 0 ) и S (это инъективная функция , область определения которой равна N ), необходимый для нетривиальности. Обратное (2) следует из свойств идентичности.
3. у = 0 ∨ ∃ х ( Sx = у )
   • Каждое число либо 0, либо является преемником некоторого числа. Схема аксиом из математической индукции , присутствующие в арифметике сильнее , чем Q превращает эту аксиому в теорему.
4. х + 0 = х
5. х + Sy = S ( х + у )
   • (4) и (5) являются рекурсивным определением из того .
6. х · 0 = 0
7. х · Sy = ( x · y ) + x
   • (6) и (7) являются рекурсивным определением из умножения .

Вариантные аксиоматизации

Аксиомы Робинсона (1950) следующие (1) - (13) у Мендельсона (1997: 200-201). Первые 6 из 13 аксиом Робинсона требуются только тогда, когда, в отличие от этого, фоновая логика не включает идентичность.

Обычный строгий общий порядок на N , «меньше чем» (обозначается «<»), может быть определен в терминах сложения с помощью правила x < y ↔ ∃ z ( Sz + x = y ) . Эквивалентно, мы получаем консервативное по определению расширение Q , принимая «<» за примитив и добавляя это правило как восьмую аксиому; эта система названа « арифметикой Робинсона R » в Boolos et al. (2002: раздел 16.4).

Другое расширение Q , которое мы временно называем Q + , получается, если мы возьмем «<» как примитив и добавим (вместо последней определяющей аксиомы) следующие три аксиомы к аксиомам (1) - (7) Q :

• ¬ ( х <0)
• х < Sy ↔ ( x < y ∨ x = y )
• х < у ∨ х = у ∨ у < х

Q + по - прежнему является консервативным расширением Q , в том смысле , что любая формула выводима в Q + , не содержащей символ «<» уже доказуемо в Q . (Добавление к Q только первых двух из трех вышеупомянутых аксиом дает консервативное расширение Q , которое эквивалентно тому, что Burgess 2005: 56 называет Q * . См. Также Burgess 2005: 230 fn. 24, но обратите внимание, что вторая из вышеперечисленных три аксиомы не могут быть выведены из «чистого дефиниционного расширения» Q, полученного добавлением только аксиомы x < y ↔ ∃ z ( Sz + x = y ) .)

Среди аксиом (1) - (7) Q аксиома (3) требует внутреннего экзистенциального квантора. Шоенфилд (1967: 22) дает аксиоматизацию, которая имеет только (неявные) внешние универсальные кванторы, отказываясь от аксиомы (3) Q, но добавляя указанные выше три аксиомы с <как примитивом. То есть система Шенфилда Q + минус аксиома (3) и строго слабее, чем Q + , поскольку аксиома (3) не зависит от других аксиом (например, ординалы меньше чем образуют модель для всех аксиом, кроме (3), когда Sv интерпретируется как v + 1). Система Шенфилда также упоминается в Boolos et al. (2002: раздел 16.2), где это называется « минимальной арифметикой » (также обозначается Q ). Близкую аксиоматизацию, в которой используется «≤» вместо «<», можно найти у Machover (1996: 256–57). ${\ displaystyle \ omega ^ {\ omega}}$

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

По метаматематике Q см. Boolos et al. (2002: глава 16), Тарский, Мостовски и Робинсон (1953), Смуллян (1991), Мендельсон (1997: 200–03) и Берджесс (2005: §§1.5a, 2.2). Предназначена интерпретацией из Q является натуральными числами и их обычным арифметический , в котором сложение и умножение имеет свое обычное значение, идентичность является равенством , Sx = х +- и 0 является натуральным числом нуля .

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

Q , как и арифметика Пеано , имеет нестандартные модели всех бесконечных мощностей . Однако, в отличие от арифметики Пеано, теорема Тенненбаума не применима к 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 Sec 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; Hájek & Pudlák 1993: 387).

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

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

Смотрите также

• Доказательство непротиворечивости Гентцена
• Теорема Гёделя о неполноте
• Список теорий первого порядка
• Аксиомы Пеано
• Пресбургерская арифметика
• Сколемская арифметика
• Арифметика второго порядка
• Теоретико-множественное определение натуральных чисел
• Общая теория множеств

использованная литература

• А. Безборуа и Джон С. Шепердсон, 1976. «Вторая теорема Гёделя о неполноте для Q». Журнал символической логики т. 41 н. 2. С. 503–512.
• Джордж Булос , Джон П. Берджесс и Ричард Джеффри , 2002. Вычислимость и логика , 4-е изд. Издательство Кембриджского университета.
• Берджесс, Джон П. , 2005. Исправление Фреге . Издательство Принстонского университета.
• Петр Гайек и Павел Пудлак (1998) [1993]. Метаматематика арифметики первого порядка , 2-е изд. Springer-Verlag.
• Лукас, младший , 1999. Концептуальные корни математики . Рутледж.
• Мачовер, Моше, 1996. Теория множеств, логика и их ограничения . Издательство Кембриджского университета.
• Мендельсон, Эллиотт , 1997. Введение в математическую логику , 4-е изд. Чепмен и Холл.
• Павел Пудлак, 1985. «Сокращения, согласованные утверждения и интерпретации». Журнал символической логики v. 50 n. 2. С. 423–441.
• В. Раутенберг (2010), Краткое введение в математическую логику (3-е изд.), Нью-Йорк: Springer Science + Business Media , DOI : 10.1007 / 978-1-4419-1221-3 , ISBN 978-1-4419-1220-6.
• Р. М. Робинсон , 1950, "Существенно неразрешимая система аксиом" в Трудах Международного математического конгресса 1950 г., стр. 729–730.
• Джозеф Р. Шенфилд , 1967. Математическая логика . Эддисон Уэсли. (Перепечатано Ассоциацией символической логики и А.К. Петерсом в 2000 г.)
• Раймонд Смуллян , 1991. Теоремы Гёделя о неполноте . Издательство Оксфордского университета.
• Альфред Тарский , А. Мостовски и Р. М. Робинсон , 1953. Неразрешимые теории . Северная Голландия.