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

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

Аксиомы [ править ]

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

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

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

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

Q интерпретируется во фрагменте Цермело аксиоматической теории множеств , состоящей из экстенсиональности , существования пустого множества и аксиомы присоединения . Эта теория — S' у Тарского, Мостовского и Робинсона (1953 , стр. 34) и ST у Берджесса (2005 , стр. 90–91, 223). см. в общей теории множеств Более подробную информацию .

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

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

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

См. также [ править ]

Ссылки [ править ]

^ Робинсон 1950 .
^ Берджесс 2005 , с. 56.
^ Булос, Берджесс и Джеффри 2002 , раздел 16.4.
^ Мендельсон 2015 , с. 188, предложение 3.24.
^ Функция $f$ говорят, что представима в $\operatorname {PA}$ если есть формула $\phi$ такой, что для всех $x_{1},\cdots ,x_{k},y$
$f({\vec {x}})=y\Longleftrightarrow \operatorname {PA} \vdash \phi ({\vec {x}},y),$

$f({\vec {x}})\neq y\Longleftrightarrow \operatorname {PA} \vdash \lnot \phi ({\vec {x}},y).$
^ Одифредди 1989 .
^ Мендельсон 2015 , с. 203, предложение 3.33.
^ Раутенберг 2010 , с. 246.
^ Безборуа и Шепердсон 1976 .
^ Пудель 1985 .
^ Гаек и Пудлак 1993 , стр. 387.

Библиография [ править ]

Безборуа, А.; Шепердсон, Джон К. (июнь 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 .

[FOOTNOTERobinson1950-1] Робинсон 1950 .

[FOOTNOTEBurgess200556-2] Берджесс 2005 , с. 56.

[FOOTNOTEBoolosBurgessJeffrey2002Sec_16.4-3] Булос, Берджесс и Джеффри 2002 , раздел 16.4.

[FOOTNOTEMendelson2015188Proposition_3.24-4] Мендельсон 2015 , с. 188, предложение 3.24.

[5] Функция $f$ говорят, что представима в $\operatorname {PA}$ если есть формула $\phi$ такой, что для всех $x_{1},\cdots ,x_{k},y$
$f({\vec {x}})=y\Longleftrightarrow \operatorname {PA} \vdash \phi ({\vec {x}},y),$

$f({\vec {x}})\neq y\Longleftrightarrow \operatorname {PA} \vdash \lnot \phi ({\vec {x}},y).$

[FOOTNOTEOdifreddi1989-6] Одифредди 1989 .

[FOOTNOTEMendelson2015203Proposition_3.33-7] Мендельсон 2015 , с. 203, предложение 3.33.

[FOOTNOTERautenberg2010246-8] Раутенберг 2010 , с. 246.

[FOOTNOTEBezboruahShepherdson1976-9] Безборуа и Шепердсон 1976 .

[FOOTNOTEPudlák1985-10] Пудель 1985 .

[FOOTNOTEHájekPudlák1993387-11] Гаек и Пудлак 1993 , стр. 387.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]