Арифметика Робинсона
В математике арифметика Робинсона представляет собой конечно аксиоматизированный фрагмент арифметики Пеано первого порядка (ПА), впервые изложенной Р. М. Робинсоном в 1950 году. [1] Обычно ее обозначают Q . Q почти PA без схемы аксиомы математической индукции . Q слабее, чем PA, но у него тот же язык, и обе теории неполны . Q важен и интересен, потому что это конечно аксиоматизированный фрагмент PA, рекурсивно незавершенный и существенно неразрешимый .
Фоновая логика Q — это логика первого порядка с тождеством , обозначаемая инфиксом '='. Индивидуумы, называемые натуральными числами , являются членами множества, называемого N , с выделенным элементом 0 , называемым нулем . Над N выполняются три операции :
Следующие аксиомы для Q — это Q1–Q7 в Burgess (2005 , стр. 42) (ср. также аксиомы арифметики первого порядка ). Переменные , не связанные квантором существования , связаны неявным квантором всеобщности .
Аксиомы Робинсона (1950) — это (1)–(13) Мендельсона (2015 , стр. 202–203). Первые 6 из 13 аксиом Робинсона требуются только тогда, когда, в отличие от этого, фоновая логика не включает тождество.
Q+ по-прежнему является консервативным расширением Q в том смысле, что любая формула, доказуемая в Q+ , не содержащая символ «< » , уже доказуема в Q. (Добавление только первых двух из трех вышеупомянутых аксиом к Q дает консервативное расширение Q , эквивалентное тому, что Берджесс (2005 , стр. 56) называет Q* . См. также Берджесс (2005 , стр. 230, сноска 24). , но обратите внимание, что вторая из трех вышеупомянутых аксиом не может быть выведена из «чистого дефиниционного расширения» Q , полученного путем добавления только аксиомы x < y ↔ ∃ z ( Sz+ х = у ) .)
Среди аксиом (1)–(7) Q аксиома (3) нуждается во внутреннем кванторе существования. Shoenfield (1967 , стр. 22) дает аксиоматизацию, которая имеет только (неявные) внешние универсальные кванторы, отказываясь от аксиомы (3) Q , но добавляя три вышеупомянутые аксиомы с < как примитивные. То есть система Шоенфилда представляет собой Q+ минус аксиома (3) и строго слабее, чем Q+ , поскольку аксиома (3) не зависит от других аксиом (например, ординалы меньше образуют модель для всех аксиом, кроме (3), когда Sv интерпретируется как v + 1). Система Шенфилда также появляется в Boolos, Burgess & Jeffrey (2002 , Sec 16.2), где она называется «минимальная арифметика » (также обозначается Q ). Тесно связанную аксиоматизацию, в которой вместо «<» используется «≤», можно найти у Machover (1996 , стр. 256–257).
