В теории множеств и математической логике арифметика первого порядка - это совокупность аксиоматических систем, формализующих натуральные и подмножества натуральных чисел. Это выбор аксиоматической теории в качестве основы для многих математических дисциплин, но не для всей. Первичной аксиомой первого порядка является арифметика Пеано , созданная Джузеппе Пеано :
-
: 0 - натуральное число.
-
: Равенство рефлексивно .
-
: Равенство симметрично .
-
: Равенство переходно .
-
: Натуральные числа замкнуты относительно равенства.
-
: Натуральные числа замкнуты относительно S (последующая операция).
-
: S - это инъекция .
-
: Не существует натурального числа, следующий за нулем.
-
: Если K - такое множество, что 0 находится в K, и для любого натурального числа n, если n находится в K, означает, что S (n) находится в K, то K содержит каждое натуральное число.
Арифметика Пеано имеет доказательства теоретико-порядковое из .
Подробнее об арифметике Пеано
Различные аксиоматизации арифметики Пеано очень разные, но эквивалентны. В то время как некоторые аксиоматизации, такие как недавно описанная (исходное определение), используют сигнатуру, содержащую только символы 0, преемника, сложения и умножения, другие аксиоматизации используют язык упорядоченного полукольца, включая дополнительный символ отношения порядка. Одна такая аксиоматизация начинается со следующих аксиом, описывающих дискретно упорядоченное полукольцо:
-
, т. е. сложение ассоциативно .
-
, т. е. сложение коммутативно .
-
, т. е. умножение ассоциативно.
-
, т. е. умножение коммутативно.
-
, т. е. умножение распределяется по сложению.
-
, т. е. ноль - это единица для сложения и поглощающий элемент для умножения.
-
, т. е. единица является тождеством для умножения.
-
, т. е. оператор '<' транзитивен .
-
, т. е. оператор '<' иррефлексивен .
-
, т. е. порядок удовлетворяет трихотомии .
-
, т.е. порядок сохраняется при добавлении того же элемента.
-
, т.е. порядок сохраняется при умножении на один и тот же положительный элемент.
-
, т. е. для любых двух различных элементов, чем больше, тем меньше плюс еще один элемент.
-
, т.е. ноль и единица различны, и между ними нет элемента.
-
, т.е. ноль - это минимальный элемент.
Эти аксиомы известны как 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 .
IΔ 0 / IΣ 1
IΔ 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 и подстановка переменных .
Нелогические аксиомы:
и рекурсивные определяющие уравнения для каждой примитивной рекурсивной функции по желанию.
использованная литература
-
^
Хейенорт, Жан (1967). От Фреге до Гёделя . п. 83. ISBN 978-0-67-432449-7.
-
^ Кэй, Ричард (1991). Модели арифметики Пеано . С. 16–18.