Арифметика первого порядка - First-order arithmetic

В теории множеств и математической логике арифметика первого порядка - это совокупность аксиоматических систем, формализующих натуральные и подмножества натуральных чисел. Это выбор аксиоматической теории в качестве основы для многих математических дисциплин, но не для всей. Первичной аксиомой первого порядка является арифметика Пеано , созданная Джузеппе Пеано :

  • : 0 - натуральное число.
  • : Равенство рефлексивно .
  • : Равенство симметрично .
  • : Равенство переходно .
  • : Натуральные числа замкнуты относительно равенства.
  • : Натуральные числа замкнуты относительно S (последующая операция).
  • : S - это инъекция .
  • : Не существует натурального числа, следующий за нулем.
  • : Если K - такое множество, что 0 находится в K, и для любого натурального числа n, если n находится в K, означает, что S (n) находится в K, то K содержит каждое натуральное число.

Арифметика Пеано имеет доказательства теоретико-порядковое из .

Подробнее об арифметике Пеано

Различные аксиоматизации арифметики Пеано очень разные, но эквивалентны. В то время как некоторые аксиоматизации, такие как недавно описанная (исходное определение), используют сигнатуру, содержащую только символы 0, преемника, сложения и умножения, другие аксиоматизации используют язык упорядоченного полукольца, включая дополнительный символ отношения порядка. Одна такая аксиоматизация начинается со следующих аксиом, описывающих дискретно упорядоченное полукольцо:

  1. , т. е. сложение ассоциативно .
  2. , т. е. сложение коммутативно .
  3. , т. е. умножение ассоциативно.
  4. , т. е. умножение коммутативно.
  5. , т. е. умножение распределяется по сложению.
  6. , т. е. ноль - это единица для сложения и поглощающий элемент для умножения.
  7. , т. е. единица является тождеством для умножения.
  8. , т. е. оператор '<' транзитивен .
  9. , т. е. оператор '<' иррефлексивен .
  10. , т. е. порядок удовлетворяет трихотомии .
  11. , т.е. порядок сохраняется при добавлении того же элемента.
  12. , т.е. порядок сохраняется при умножении на один и тот же положительный элемент.
  13. , т. е. для любых двух различных элементов, чем больше, тем меньше плюс еще один элемент.
  14. , т.е. ноль и единица различны, и между ними нет элемента.
  15. , т.е. ноль - это минимальный элемент.

Эти аксиомы известны как PA - ; теория PA получается добавлением индукционной схемы первого порядка . Важная особенность PA - это то, что любая структура, удовлетворяющая этой теории, имеет начальный сегмент (упорядоченный по ), изоморфный . Элементы в этом сегменте называются стандартными элементами, а другие элементы - нестандартными.

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

Арифметика Робинсона - это конечно аксиоматизированный фрагмент арифметики Пеано (PA) первого порядка, впервые созданный в 1950 году Р. М. Робинсоном . Его часто называют Q. Q почти идентичен PA без математической схемы аксиомы индукции (PA - ). Q слабее, чем PA, но их язык тот же, и обе теории неполны . Фоновая логика Q - это логика первого порядка с идентичностью, обозначаемая инфиксом '='. Индивидуумы, называемые натуральными числами, являются членами множества, называемого N, с выделенным элементом 0, называемым нулем. Над N выполняются три операции:

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

Аксиомы следующие:

  • : 0 не является преемником какого-либо числа.
  • : Если преемник x идентичен преемнику y, то x и y идентичны.
  • Каждое натуральное число либо 0, либо является наследником некоторого числа.

Арифметика Робинсона имеет теоретико-доказательный ординал .

Повторяющиеся индуктивные определения

Система многократно повторяемых индуктивных определений представляет собой иерархию сильных математических систем, разработанную немецким математиком Вильфридом Бухгольцем, хорошо известным созданием пси-функции Бухгольца . ID ν расширяет PA с помощью ν итерационных наименьших неподвижных точек монотонных операторов. Если ν = ω, аксиомы следующие:

  • Аксиомы из арифметики Пеано
  • для любой L ID -формулы F (x)

Для ν ≠ ω аксиомы следующие:

  • Аксиомы из арифметики Пеано
  • для любой L ID -формулы F (x) и всех u <ν

ослабленная версия . В системе , набор вместо этого называется индуктивно определяются , если для некоторых монотонного оператора , является фиксированной точкой , а не мере фиксированной точки. Эта небольшая разница делает систему значительно слабее:, а .

будет ослаблен еще больше. В , он не только использует неподвижные точки, а не наименьшие неподвижные точки, но также имеет индукцию только для положительных формул. Это еще раз тонкое различие делает систему еще слабее:, while .

самый слабый из всех вариантов , основанный на W-типах. Величина ослабления по сравнению с регулярными повторяющимися индуктивными определениями идентична удалению индукции стержня при определенной подсистеме арифметики второго порядка . , пока .

является "разворачивающимся" усилением . Это не совсем арифметическая система первого порядка, но она отражает то, что можно получить с помощью предикативных рассуждений, основанных на ν-кратном повторении обобщенных индуктивных определений. Величина увеличения силы идентична увеличению от до :, в то время как .

это автоморфизм из . , но все равно слабее .

это автоморфизм из . , но все равно слабее .

является автоморфизмом . , где - иерархия Веблена со счетно повторяемыми наименьшими фиксированными точками.

Другие системы первого порядка

PA -

PA - теория первого порядка неотрицательной части дискретно упорядоченного кольца. Кольцо - это набор, оснащенный двумя бинарными операциями: (сложение) и (умножение), удовлетворяющий следующим трем наборам аксиом, называемым аксиомами кольца:

  • ассоциативно, коммутативно, является тождественным добавком , и является присадкой обратным из .
  • ассоциативно и является мультипликативным тождеством .
  • для всех , и в .
  • для всех , и в .

PA - имеет теоретико-доказательный порядковый номер .

RFA

RFA - это элементарная арифметика функций . Элементарная функция - это функция, которая может быть получена с помощью следующих операций:

  • рудиментарен
  • рудиментарен
  • рудиментарен
  • Любая композиция рудиментарных функций рудиментарна.
  • рудиментарен

Для любого множества M пусть rud ( M ) будет наименьшим множеством, содержащим M ∪ { M }, замкнутым относительно рудиментарных операций. RFA - это версия арифметики, основанная на элементарных функциях. RFA имеет теоретико-доказательный ординал ω 2 .

0 / IΣ 1

0 и IΣ 1 являются базовой арифметикой с индукцией для Δ 0 - и Σ 1 -предикатов соответственно. Обратите внимание, что когда люди ссылаются на IΔ 0 , IΔ 0 является базовой арифметикой с индукцией для Δ 0 -предикатов, но без аксиомы, утверждающей, что возведение в степень является полным , в то время как IΔ 0 с такой аксиомой упоминается как IΔ 0 + . IΔ 0 п 1 <п <со является IΔ 0 + дополняется аксиомой гарантируя , что каждый элемент п -го уровня в иерархии Гжегорчика является полным. IΔ 0 имеет теоретико-доказательный ординал ω 2 . IΔ 0 + . имеет теоретико-доказательный ординал ω 3 . IΔ 0 n имеет теоретико-доказательный ординал ω n . IΣ 1 имеет теоретико-доказательный ординал ω ω .

ОДВ

EFA - это арифметика элементарных функций. Его язык содержит:

  • две константы 0, 1,
  • три бинарные операции +, ×, exp, где exp ( x , y ) обычно записывается как x y ,
  • символ двоичного отношения <(в этом нет необходимости, поскольку он может быть записан в терминах других операций и иногда опускается, но удобен для определения ограниченных кванторов).

Ограниченные кванторы - это кванторы вида ∀ (x <y) и ∃ (x <y), которые являются сокращениями для ∀ x (x <y) → ... и ∃x (x <y) ∧ ... в обычном способ. Аксиомы ОДВ таковы:

  • Аксиомы арифметики Робинсона для 0, 1, +, ×, <
  • Аксиомы возведения в степень: x 0 = 1, x y +1 = x y × x .
  • Индукция для формул, все кванторы которых ограничены (но могут содержать свободные переменные).

PRA

PRA - это примитивная рекурсивная арифметика, бескванторная формализация натуральных чисел . Язык PRA состоит из:

Логические аксиомы PRA:

Логические правила PRA - это modus ponens и подстановка переменных .

Нелогические аксиомы:

и рекурсивные определяющие уравнения для каждой примитивной рекурсивной функции по желанию.

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

  1. ^ Хейенорт, Жан (1967). От Фреге до Гёделя . п. 83. ISBN 978-0-67-432449-7.
  2. ^ Кэй, Ричард (1991). Модели арифметики Пеано . С. 16–18.