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

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

Аксиомы

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

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

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

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

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

Аксиомы Робинсона (1950) : (1)–(13) у Мендельсона (2015 , стр. 202–203). Первые 6 из 13 аксиом Робинсона необходимы только тогда, когда, в отличие от этого случая, базовая логика не включает идентичность.

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

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

• ¬( х < 0)
• Икс < Sy ↔ ( Икс < y ∨ Икс знак равно y )
• x < y ∨ x = y ∨ y < x

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

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

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

О метаматематике Q см. Boolos, Burgess & Jeffrey (2002 , chpt. 16), Tarski, Mostowski & Robinson (1953) , Smullyan (1991) , Mendelson (2015 , стр. 202–203) и Burgess (2005 , §§). 1.5а, 2.2). Предполагаемая интерпретация Q = — это натуральные числа в которой сложение и умножение имеют свой обычный смысл, тождество — равенство , Sx и их обычная арифметика , x + 1, а 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' у Тарского, Мостовского и Робинсона (1953 , стр. 34) и ST у Берджесса (2005 , стр. 90–91, 223). см. в общей теории множеств Более подробную информацию .

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

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

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

См. также

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

Библиография

• Безборуа, А.; Шепердсон, Джон К. (июнь 1976 г.). «Вторая теорема Гёделя о неполноте для Q». Журнал символической логики . 41 (2): 503–512. дои : 10.2307/2272251 . JSTOR   2272251 .
• Булос, Джордж ; Берджесс, Джон П .; Джеффри, Ричард (2002). Вычислимость и логика (4-е изд.). Издательство Кембриджского университета . ISBN  0-521-00758-5 .
• Берджесс, Джон П. (июль 2005 г.). Исправление Фреге . Издательство Принстонского университета . ISBN  978-0691122311 .
• Гаек, Петр; Пудлак, Павел (1993). Метаматематика арифметики первого порядка (2-е изд.). Спрингер-Верлаг .
• Джонс, Джеймс П.; Шепердсон, Джон К. (1983). «Варианты принципиально неразрешимой теории Робинсона R». Архив математической логики и фундаментальных исследований . 23 :61-64. дои : 10.1007/BF02023013 . S2CID   2659126 .
• Лукас, Джон Р. Концептуальные корни математики . Рутледж.
• Мачовер, Моше (1996). Теория множеств, логика и их ограничения . Издательство Кембриджского университета .
• Мендельсон, Эллиотт (2015). Введение в математическую логику (6-е изд.). Чепмен и Холл. ISBN  9781482237726 .
• Одифредди, Пьерджорджо (1989). Классическая теория рекурсии, Vol. 1 (Теория функций и множеств натуральных чисел) . Исследования по логике и основам математики. Том. 125. Северная Голландия. ISBN  9780444894830 .
• Пудлак, Павел (июнь 1985 г.). «Сокращения, последовательность заявлений и интерпретаций». Журнал символической логики . 50 (2): 423–441. дои : 10.2307/2274231 . JSTOR   2274231 . S2CID   30289163 .
• Раутенберг, Вольфганг (2010). Краткое введение в математическую логику (3-е изд.). Нью-Йорк: Springer Science + Business Media . дои : 10.1007/978-1-4419-1221-3 . ISBN  978-1-4419-1220-6 . .
• Робинсон, Рафаэль М. (1950). «По существу неразрешимая система аксиом». Труды Международного математического конгресса : 729–730.
• Шенфилд, Джозеф Р. (1967). Математическая логика . Эддисон Уэсли. (Перепечатано Ассоциацией символической логики и А.К. Петерсом в 2000 г.).
• Смалльян, Раймонд (1991). Теоремы Гёделя о неполноте . Издательство Оксфордского университета .
• Тарский, Альфред ; Мостовский, Анджей ; Робинсон, Рафаэль М. (1953). Неразрешимые теории . Северная Голландия.
• Воот, Роберт Л. (1966). «О теореме Кобэма относительно неразрешимых теорий». Исследования по логике и основам математики . 44 : 14–25. дои : 10.1016/S0049-237X(09)70566-X . ISBN  9780804700962 .