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

Аксиоматическая логическая система

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

Аксиомы

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

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

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

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

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

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

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

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

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

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

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

О метаматематике Q см. Boolos, Burgess & Jeffrey (2002, chpt. 16), Tarski, Mostowski & Robinson (1953), Smullyan (1991), Mendelson (2015, pp. 202–203) и Burgess (2005, §§1.5a, 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' в Tarski, Mostowski & Robinson (1953, стр. 34) и ST в Burgess (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 является неполной и неразрешимой. Это указывает на то, что неполнота и неразрешимость PA не могут быть возложены на единственный аспект PA, отличающий его от Q , а именно на схему аксиом индукции .

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

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

Ссылки

↑ Робинсон 1950.
^ Берджесс 2005, стр. 56.
^ Булос, Берджесс и Джеффри 2002, раздел 16.4.
^ Мендельсон 2015, стр. 188, Предложение 3.24.
^ Говорят, что функция представима в , если существует формула такая, что для всех $f$ $\operatorname {PA}$ $\фи$ $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.

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

Bezboruah, A.; Shepherdson, John C. (июнь 1976 г.). «Вторая теорема Гёделя о неполноте для Q». Journal of Symbolic Logic . 41 (2): 503– 512. doi :10.2307/2272251. JSTOR 2272251.
Булос, Джордж ; Берджесс, Джон П.; Джеффри , Ричард (2002). Вычислимость и логика (4-е изд.). Cambridge University Press . ISBN 0-521-00758-5.
Берджесс, Джон П. (июль 2005 г.). Fixing Frege . Princeton University Press . ISBN 978-0691122311.
Гайек, Петр; Пудлак, Павел (1993). Метаматематика арифметики первого порядка (2-е изд.). Спрингер-Верлаг .
Джонс, Джеймс П.; Шепердсон, Джон К. (1983). «Варианты принципиально неразрешимой теории Робинсона R». Archiv für mathematische Logik und Grundlagenforschung . 23 : 61–64 . doi : 10.1007/BF02023013. S2CID 2659126.
Лукас, Джон Р. Концептуальные корни математики . Routledge.
Machover, Moshé (1996). Теория множеств, логика и их ограничения . Cambridge University Press .
Мендельсон, Эллиотт (2015). Введение в математическую логику (6-е изд.). Chapman & Hall. ISBN 9781482237726.
Одифредди, Пьерджорджио (1989). Классическая теория рекурсии, т. 1 (Теория функций и множеств натуральных чисел) . Исследования по логике и основаниям математики. Т. 125. Северная Голландия. ISBN 9780444894830.
Пудлак, Павел (июнь 1985 г.). «Сокращения, утверждения о согласованности и интерпретации». Журнал символической логики . 50 (2): 423– 441. doi :10.2307/2274231. JSTOR 2274231. S2CID 30289163.
Раутенберг, Вольфганг (2010). Краткое введение в математическую логику (3-е изд.). Нью-Йорк: Springer Science+Business Media . doi :10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6..
Робинсон, Рафаэль М. (1950). «По существу неразрешимая система аксиом». Труды Международного математического конгресса : 729–730 .
Шенфилд, Джозеф Р. (1967). Математическая логика . Эддисон Уэсли. (Переиздано Ассоциацией символической логики и AK Peters в 2000 г.).
Смаллиан, Рэймонд (1991). Теоремы Гёделя о неполноте . Oxford University Press .
Тарский, Альфред ; Мостовский, Анджей ; Робинсон, Рафаэль М. (1953). Неразрешимые теории . Северная Голландия.
Vaught, Robert L. (1966). «О теореме Кобэма относительно неразрешимых теорий». Исследования по логике и основаниям математики . 44 : 14– 25. doi :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}$ $\фи$ $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.