Аксиомы Пеано

Аксиомы натуральных чисел

В математической логике аксиомы Пеано ( / p i ˈ ɑː n oʊ / , ^[1] [peˈaːno] ), также известные как аксиомы Дедекинда-Пеано или постулаты Пеано , являются аксиомами натуральных чисел , представленными 19-м веком. Итальянский математик Джузеппе Пеано . Эти аксиомы использовались почти без изменений в ряде метаматематических исследований, включая исследования фундаментальных вопросов о том, является ли теория чисел последовательной и полной .

Важность формализации арифметики не была оценена должным образом до работы Германа Грассмана , который в 1860-х годах показал, что многие факты в арифметике могут быть выведены из более фундаментальных фактов о последующих операциях и индукции . ^{[2] [3]} В 1881 году Чарльз Сандерс Пирс представил аксиоматизацию арифметики натуральных чисел. ^{[4] [5]} В 1888 году Ричард Дедекинд предложил еще одну аксиоматизацию арифметики натуральных чисел, а в 1889 году Пеано опубликовал упрощенную версию их в виде сборника аксиом в своей книге « Принципы арифметики, представленные новым методом» ( лат. : Принципы арифметики, новый метод экспозита ).

Девять аксиом Пеано содержат три типа утверждений. Первая аксиома утверждает существование хотя бы одного члена множества натуральных чисел. Следующие четыре являются общими утверждениями о равенстве ; в современных трактовках они часто рассматриваются не как часть аксиом Пеано, а скорее как аксиомы «основной логики». ^[6] Следующие три аксиомы представляют собой утверждения первого порядка о натуральных числах, выражающие фундаментальные свойства последующей операции. Девятая, последняя аксиома — это утверждение второго порядка принципа математической индукции по натуральным числам, что делает эту формулировку близкой к арифметике второго порядка . Более слабая система первого порядка, называемая арифметикой Пеано , получается путем явного добавления символов операций сложения и умножения и замены аксиомы индукции второго порядка схемой аксиом первого порядка .

Историческая формулировка второго порядка

Когда Пеано сформулировал свои аксиомы, язык математической логики находился в зачаточном состоянии. Система логических обозначений, которую он создал для представления аксиом, не оказалась популярной, хотя она и послужила источником современной записи членства во множестве (ε, которая происходит от ε Пеано). Пеано проводил четкое различие между математическими и логическими символами, что еще не было распространено в математике; такое разделение было впервые введено в Begriffsschrift Готлоба Фреге , опубликованном в 1879 году. ^[7] Пеано не знал о работах Фреге и самостоятельно воссоздал свой логический аппарат на основе работ Буля и Шредера . ^[8]

Аксиомы Пеано определяют арифметические свойства натуральных чисел , обычно представленных в виде набора N или Нелогические символы аксиом состоят из постоянного символа 0 и символа унарной функции S. ${\displaystyle \mathbb {N} .}$

Первая аксиома гласит, что константа 0 является натуральным числом:

1. 0 – натуральное число.

В первоначальной формулировке аксиом Пеано в качестве «первого» натурального числа использовалась 1 вместо 0, ^[9] тогда как аксиомы в Formulario Mathematico включают ноль. ^[10]

Следующие четыре аксиомы описывают отношение равенства . Поскольку они логически действительны в логике первого порядка с равенством, они не считаются частью «аксиом Пеано» в современных трактовках. ^[8]

2. Для каждого натурального числа x x = x . То есть равенство рефлексивно .
3. Для всех натуральных чисел x и y , если x = y , то y = x . То есть равенство симметрично .
4. Для всех натуральных чисел x , y и z , если x = y и y = z , то x = z . То есть равенство транзитивно .
5. Для всех a и b , если b — натуральное число и a = b , то a также является натуральным числом. То есть натуральные числа замкнуты относительно равенства.

Остальные аксиомы определяют арифметические свойства натуральных чисел. Предполагается , что натуральные числа замкнуты относительно однозначной функции « преемника » S.

6. Для каждого натурального числа n S ( n ) является натуральным числом. То есть натуральные числа замкнуты относительно S.
7. Для всех натуральных чисел m и n , если S ( m ) = S ( n ) , то m = n . То есть S — это инъекция .
8. Для каждого натурального числа n S ( n ) = 0 неверно. То есть не существует натурального числа, наследником которого был бы 0.

Цепочка светлых домино, начиная с ближайшего, может представлять собой N , ^{[примечание 1] [11] [12]} , однако аксиомам 1–8 также удовлетворяет набор всех светлых и темных домино. ^{[примечание 2]} 9-я аксиома ( индукция ) ограничивает N цепочкой из легких фигур («никакого мусора»), поскольку только легкие домино падают, когда ближайший падает. ^[13]

Аксиомы 1, 6, 7, 8 определяют одноместное представление интуитивного понятия натуральных чисел: число 1 можно определить как S (0), 2 как S ( S (0)) и т.д. Однако, учитывая понятие натуральные числа, определенные этими аксиомами, аксиомы 1, 6, 7, 8 не означают, что функция-преемник генерирует все натуральные числа, отличные от 0.

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

9. Если K — такое множество, что:
   • 0 находится в K и
   • для каждого натурального числа n нахождение n в K означает, что S ( n ) находится в K ,
   тогда K содержит все натуральные числа.

Аксиому индукции иногда формулируют в следующем виде:

9. Если φ — унарный предикат такой, что:
   • φ (0) истинно, и
   • для каждого натурального числа n истинность φ(n) означает, что истинность φ ( S ( n ) )
   тогда φ ( n ) верно для любого натурального числа n .

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

Определение арифметических операций и отношений

Если мы используем аксиому индукции второго порядка, можно определить сложение , умножение и полный (линейный) порядок на N непосредственно с помощью аксиом. Однако при индукции первого ^{порядка} это невозможно, ^{и сложение} и умножение часто добавляются в качестве аксиом. Соответствующие функции и отношения строятся в теории множеств или логике второго порядка , и их уникальность можно показать с помощью аксиом Пеано.

Добавление

Сложение — это функция, которая отображает два натуральных числа (два элемента N ) в другое. Он определяется рекурсивно как:

${\displaystyle {\begin{aligned}a+0&=a,&{\textrm {(1)}}\\a+S(b)&=S(a+b).&{\textrm {(2)}}\end{aligned}}}$

Например:

${\displaystyle {\begin{aligned}a+1&=a+S(0)&{\mbox{by definition}}\\&=S(a+0)&{\mbox{using (2)}}\\&=S(a),&{\mbox{using (1)}}\\\\a+2&=a+S(1)&{\mbox{by definition}}\\&=S(a+1)&{\mbox{using (2)}}\\&=S(S(a))&{\mbox{using }}a+1=S(a)\\\\a+3&=a+S(2)&{\mbox{by definition}}\\&=S(a+2)&{\mbox{using (2)}}\\&=S(S(S(a)))&{\mbox{using }}a+2=S(S(a))\\{\text{etc.}}&\\\end{aligned}}}$

Структура ( N , + ) представляет собой коммутативный моноид с единичным элементом 0. ( N , + ) также является сокращающейся магмой и, следовательно , вкладывается в группу . Наименьшая группа, включающая N , — это целые числа .

Умножение

Аналогично, умножение — это функция, переводящая два натуральных числа в другое. Учитывая сложение, он определяется рекурсивно как:

${\displaystyle {\begin{aligned}a\cdot 0&=0,\\a\cdot S(b)&=a+(a\cdot b).\end{aligned}}}$

Легко видеть, что это мультипликативное правое тождество : ${\displaystyle S(0)}$

${\displaystyle a\cdot S(0)=a+(a\cdot 0)=a+0=a}$

Чтобы показать, что это также мультипликативная левая идентичность, требуется аксиома индукции из-за способа определения умножения: ${\displaystyle S(0)}$

• ${\displaystyle S(0)}$является левым тождеством 0: . ${\displaystyle S(0)\cdot 0=0}$
• Если является левым тождеством (то есть ), то также является левым тождеством : . ${\displaystyle S(0)}$ ${\displaystyle a}$ ${\displaystyle S(0)\cdot a=a}$ ${\displaystyle S(0)}$ ${\displaystyle S(a)}$ ${\displaystyle S(0)\cdot S(a)=S(0)+S(0)\cdot a=S(0)+a=a+S(0)=S(a+0)=S(a)}$

Следовательно, по аксиоме индукции есть мультипликативная левая единица всех натуральных чисел. Более того, можно показать, что умножение коммутативно и распределяется по сложению: ${\displaystyle S(0)}$

${\displaystyle a\cdot (b+c)=(a\cdot b)+(a\cdot c)}$.

Таким образом, – коммутативное полукольцо . ${\displaystyle (\mathbb {N} ,+,0,\cdot ,S(0))}$

Неравенства

Обычное отношение полного порядка ≤ для натуральных чисел можно определить следующим образом, предполагая, что 0 — натуральное число:

Для всех a , b ∈ N , a ⩽ b тогда и только тогда, когда существует такой c ∈ N , что a + c = b .

Это отношение устойчиво относительно сложения и умножения: при , если a ≤ b , то: ${\displaystyle a,b,c\in \mathbb {N} }$

• a + c ≤ b + c и
• а · c ≤ б · c .

Таким образом, структура ( N , +, ·, 1, 0, ≤) является упорядоченным полукольцом ; поскольку между 0 и 1 нет натурального числа, это дискретное упорядоченное полукольцо.

Аксиому индукции иногда формулируют в следующей форме, в которой используется более сильная гипотеза с использованием отношения порядка «≤»:

Для любого предиката ф , если

• φ (0) истинно, и
• для каждого n ∈ N , если φ ( k ) истинно для каждого k ∈ N такого, что k ≤ n , то φ ( S ( n )) истинно,
• тогда для каждого n ∈ N истинно φ ( n ).

Эта форма аксиомы индукции, называемая сильной индукцией , является следствием стандартной формулировки, но часто лучше подходит для рассуждений о порядке ≤. Например, чтобы показать, что натуральные числа хорошо упорядочены — каждое непустое подмножество N имеет наименьший элемент — можно рассуждать следующим образом. Пусть задан непустой X ⊆ N и предположим , что X не имеет наименьшего элемента.

• Поскольку 0 — наименьший элемент N , должно быть так, что 0 ∉ X.
• Предположим , что для любого n ∈ N для каждого k ≤ n k ∉ X. Тогда S ( n ) ∉ X , иначе это был бы наименьший элемент X.

Таким образом , по принципу сильной индукции для любого n ∈ N n ∉ X . Таким образом, X ∩ N = ∅ , что противоречит тому , что X является непустым подмножеством N. Таким образом, X имеет наименьший элемент.

Модели

Моделью аксиом Пеано является тройка ( N , 0, S ) , где N — (обязательно бесконечное) множество, 0 ∈ N и S : N → N удовлетворяет аксиомам, указанным выше. Дедекинд доказал в своей книге 1888 года « Природа и значение чисел» ( нем . Was sind und Was sollen die Zahlen?, т. е. «Что такое числа и для чего они нужны?»), что любые две модели аксиом Пеано ( включая аксиому индукции второго порядка) изоморфны . В частности, для данных двух моделей ( NA _, 0 _A , S _A ) и ( N _B , 0 _B , SB ₎ аксиом Пеано существует единственный гомоморфизм f  : NA → N _B , удовлетворяющий _{условиям}

${\displaystyle {\begin{aligned}f(0_{A})&=0_{B}\\f(S_{A}(n))&=S_{B}(f(n))\end{aligned}}}$

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

Теоретико-множественные модели

Аксиомы Пеано могут быть получены из теоретико-множественных конструкций натуральных чисел и аксиом теории множеств, таких как ZF . ^[14] Стандартная конструкция натуральных чисел, предложенная Джоном фон Нейманом , начинается с определения 0 как пустого множества ∅ и оператора s на множествах, определяемых как:

${\displaystyle s(a)=a\cup \{a\}}$

Множество натуральных чисел N определяется как пересечение всех замкнутых относительно s множеств , содержащих пустое множество. Каждое натуральное число равно (как множество) множеству натуральных чисел, меньших его:

${\displaystyle {\begin{aligned}0&=\emptyset \\1&=s(0)=s(\emptyset )=\emptyset \cup \{\emptyset \}=\{\emptyset \}=\{0\}\\2&=s(1)=s(\{0\})=\{0\}\cup \{\{0\}\}=\{0,\{0\}\}=\{0,1\}\\3&=s(2)=s(\{0,1\})=\{0,1\}\cup \{\{0,1\}\}=\{0,1,\{0,1\}\}=\{0,1,2\}\end{aligned}}}$

и так далее. Множество N вместе с 0 и функцией-преемником s  : N → N удовлетворяет аксиомам Пеано.

Арифметика Пеано равносовместима с несколькими слабыми системами теории множеств. ^[15] Одной из таких систем является ZFC, в которой аксиома бесконечности заменена ее отрицанием. Другая такая система состоит из общей теории множеств ( экстенсиональность , существование пустого множества и аксиома присоединения ), дополненной схемой аксиом, утверждающей, что свойство, которое справедливо для пустого множества и справедливо для присоединения всякий раз, когда оно справедливо для присоединения. должно соблюдаться для всех наборов.

Интерпретация в теории категорий

Аксиомы Пеано также можно понять с помощью теории категорий . Пусть C — категория с терминальным объектом 1 _C и определите категорию точечных унарных систем US ₁ ( C ) следующим образом:

• Объектами US ₁ ( C ) являются тройки ( X , 0 _X , S _X ) , где X — объект C , а 0 _X  : 1 _C → X и S _X  : X → X — C - морфизмы.
• Морфизм φ  : ( X , 0 _X , S _X ) → ( Y , 0 _Y , S _Y ) — это C -морфизм φ  : X → Y с φ 0 _X = 0 _Y и φ S _X = S _Y φ .

Тогда говорят, что C удовлетворяет аксиомам Дедекинда – Пеано, если US ₁ ( C ) имеет начальный объект; этот исходный объект известен как объект натурального числа в C. Если ( N , 0, S ) — этот исходный объект, а ( X , 0 _X , S _X ) — любой другой объект, то уникальное отображение u  : ( N , 0, S ) → ( X , 0 _X , S _X ) таков, что

${\displaystyle {\begin{aligned}u(0)&=0_{X},\\u(Sx)&=S_{X}(ux).\end{aligned}}}$

Это и есть рекурсивное определение 0 _X и S _X .

Последовательность

Когда аксиомы Пеано были впервые предложены, Бертран Рассел и другие согласились, что эти аксиомы неявно определяют, что мы подразумеваем под «натуральным числом». ^[16] Анри Пуанкаре был более осторожен, говоря, что они определяют натуральные числа только в том случае, если они непротиворечивы ; если существует доказательство, которое начинается только с этих аксиом и приводит к противоречию, такому как 0 = 1, то аксиомы противоречивы и ничего не определяют. ^[17] В 1900 году Дэвид Гильберт поставил задачу доказательства их непротиворечивости с использованием только финитистских методов в качестве второй из своих двадцати трёх задач . ^[18] В 1931 году Курт Гёдель доказал свою вторую теорему о неполноте , которая показывает, что такое доказательство непротиворечивости не может быть формализовано внутри самой арифметики Пеано, если арифметика Пеано непротиворечива. ^[19]

Хотя широко утверждается, что теорема Гёделя исключает возможность финитистского доказательства непротиворечивости арифметики Пеано, это зависит от того, что именно понимать под финитистским доказательством. Сам Гёдель указывал на возможность дать финитистское доказательство непротиворечивости арифметики Пеано или более сильных систем с помощью финитистских методов, которые не формализуемы в арифметике Пеано, и в 1958 году Гёдель опубликовал метод доказательства непротиворечивости арифметики с использованием теории типов . ^[20] В 1936 году Герхард Генцен дал доказательство непротиворечивости аксиом Пеано, используя трансфинитную индукцию до порядкового номера , называемого ε 0 . ^[21] Генцен объяснил: «Цель настоящей статьи — доказать непротиворечивость элементарной теории чисел или, скорее, свести вопрос непротиворечивости к некоторым фундаментальным принципам». Доказательство Генцена, возможно, является финитистским, поскольку трансфинитный ординал ε ₀ может быть закодирован в терминах конечных объектов (например, как машина Тьюринга , описывающая подходящий порядок целых чисел, или, более абстрактно, как состоящая из конечных деревьев , соответствующим образом линейно упорядоченных) . Неясно, отвечает ли доказательство Генцена требованиям, предусмотренным Гильбертом: не существует общепринятого определения того, что именно подразумевается под финитистским доказательством, а сам Гильберт никогда не давал точного определения.

Подавляющее большинство современных математиков считают, что аксиомы Пеано непротиворечивы, полагаясь либо на интуицию, либо на принятие доказательства непротиворечивости, такого как доказательство Генцена . Небольшое количество философов и математиков, некоторые из которых также выступают за ультрафинитизм , отвергают аксиомы Пеано, потому что принятие аксиом равносильно признанию бесконечного набора натуральных чисел. В частности, предполагается, что сложение (включая функцию-преемник) и умножение являются полными . Любопытно, что существуют самопроверяющиеся теории , подобные ПА, но имеющие вычитание и деление вместо сложения и умножения, которые аксиоматизируются таким образом, чтобы избежать доказательства предложений, соответствующих совокупности сложения и умножения, но которые все же способны чтобы доказать все истинные теоремы PA, и, тем не менее, может быть расширено до непротиворечивой теории, которая доказывает свою собственную непротиворечивость (заявленную как отсутствие доказательства в стиле Гильберта «0 = 1»). ^[22] ${\displaystyle \Pi _{1}}$

Арифметика Пеано как теория первого порядка

Все аксиомы Пеано, за исключением девятой аксиомы (аксиомы индукции), являются утверждениями логики первого порядка . ^[23] Арифметические операции сложения и умножения, а также отношение порядка также могут быть определены с использованием аксиом первого порядка. Приведенная выше аксиома индукции имеет второй порядок , поскольку она дает количественную оценку предикатам (т. е. множествам натуральных чисел, а не натуральных чисел). В качестве альтернативы можно рассмотреть схему аксиом индукции первого порядка. Такая схема включает в себя одну аксиому на каждый предикат, определяемый на языке арифметики Пеано первого порядка, что делает ее более слабой, чем аксиома второго порядка. ^[24] Причина, по которой он слабее, заключается в том, что количество предикатов в языке первого порядка счетно, тогда как количество наборов натуральных чисел несчетно. Таким образом, существуют множества, которые невозможно описать на языке первого порядка (фактически большинство множеств обладают этим свойством).

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

Для этой цели достаточен следующий список аксиом (наряду с обычными аксиомами равенства), содержащий шесть из семи аксиом арифметики Робинсона : ^[25]

• ${\displaystyle \forall x\ (0\neq S(x))}$
• ${\displaystyle \forall x,y\ (S(x)=S(y)\Rightarrow x=y)}$
• ${\displaystyle \forall x\ (x+0=x)}$
• ${\displaystyle \forall x,y\ (x+S(y)=S(x+y))}$
• ${\displaystyle \forall x\ (x\cdot 0=0)}$
• ${\displaystyle \forall x,y\ (x\cdot S(y)=x\cdot y+x)}$

Помимо этого списка числовых аксиом, арифметика Пеано содержит схему индукции, состоящую из рекурсивно перечислимого и даже разрешимого набора аксиом . Для каждой формулы φ ( x , y ₁ , ..., y _k ) на языке арифметики Пеано аксиомой индукции первого порядка для φ является предложение

${\displaystyle \forall {\bar {y}}{\Bigg (}{\bigg (}\varphi (0,{\bar {y}})\land \forall x{\Big (}\varphi (x,{\bar {y}})\Rightarrow \varphi (S(x),{\bar {y}}){\Big )}{\bigg )}\Rightarrow \forall x\varphi (x,{\bar {y}}){\Bigg )}}$

где – сокращение для y ₁ ,..., y _k . Схема индукции первого порядка включает в себя каждый экземпляр аксиомы индукции первого порядка; то есть он включает аксиому индукции для каждой формулы φ . ${\displaystyle {\bar {y}}}$

Эквивалентные аксиоматизации

Приведенная выше аксиоматизация арифметики Пеано использует сигнатуру, которая имеет только символы нуля, а также операции-преемники, сложения и умножения. Есть много других различных, но эквивалентных аксиоматизаций. Одна из таких альтернатив ^[26] использует символ отношения порядка вместо операции-преемника и язык дискретно упорядоченных полуколец (аксиомы 1–7 для полуколец, 8–10 по порядку, 11–13 по совместимости и 14–15 по дискретности). :

1. ${\displaystyle \forall x,y,z\ ((x+y)+z=x+(y+z))}$, т. е. сложение ассоциативно .
2. ${\displaystyle \forall x,y\ (x+y=y+x)}$, т. е. сложение коммутативно .
3. ${\displaystyle \forall x,y,z\ ((x\cdot y)\cdot z=x\cdot (y\cdot z))}$, т. е. умножение ассоциативно.
4. ${\displaystyle \forall x,y\ (x\cdot y=y\cdot x)}$, т. е. умножение коммутативно.
5. ${\displaystyle \forall x,y,z\ (x\cdot (y+z)=(x\cdot y)+(x\cdot z))}$, т. е. умножение распределяет над сложением.
6. ${\displaystyle \forall x\ (x+0=x\land x\cdot 0=0)}$, т. е. ноль является тождеством для сложения и поглощающим элементом для умножения (фактически излишним ^{[примечание 3]} ).
7. ${\displaystyle \forall x\ (x\cdot 1=x)}$, т. е. единица является тождеством для умножения.
8. ${\displaystyle \forall x,y,z\ (x<y\land y<z\Rightarrow x<z)}$, т. е. оператор '<' является транзитивным .
9. ${\displaystyle \forall x\ (\neg (x<x))}$, т. е. оператор '<' иррефлексивен .
10. ${\displaystyle \forall x,y\ (x<y\lor x=y\lor y<x)}$, т. е. упорядочение удовлетворяет трихотомии .
11. ${\displaystyle \forall x,y,z\ (x<y\Rightarrow x+z<y+z)}$, т.е. порядок сохраняется при добавлении одного и того же элемента.
12. ${\displaystyle \forall x,y,z\ (0<z\land x<y\Rightarrow x\cdot z<y\cdot z)}$, т.е. порядок сохраняется при умножении на один и тот же положительный элемент.
13. ${\displaystyle \forall x,y\ (x<y\Rightarrow \exists z\ (x+z=y))}$, т.е. для любых двух различных элементов, чем больше, тем меньше плюс еще один элемент.
14. ${\displaystyle 0<1\land \forall x\ (x>0\Rightarrow x\geq 1)}$, т.е. ноль и единица различны и между ними нет элемента. Другими словами, 0 покрывается 1 , что говорит о том, что эти числа дискретны.
15. ${\displaystyle \forall x\ (x\geq 0)}$, т.е. ноль является минимальным элементом.

Теория, определяемая этими аксиомами, известна как PA ⁻ . Она также неполна, и одно из ее важных свойств состоит в том, что любая структура, удовлетворяющая этой теории, имеет начальный сегмент (упорядоченный ), изоморфный . Элементы в этом сегменте называются стандартными элементами, а другие элементы называются нестандартными элементами. ${\displaystyle M}$ ${\displaystyle \leq }$ ${\displaystyle \mathbb {N} }$

Наконец, арифметика Пеано PA получается добавлением схемы индукции первого порядка.

Неразрешимость и неполнота

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

Из этого, тесно связанного с приведенным выше результатом о неполноте (через теорему Гёделя о полноте для FOL), следует, что не существует алгоритма для определения того, является ли данное предложение FOL следствием аксиоматизации первого порядка арифметики Пеано или нет. Следовательно, PA является примером неразрешимой теории . Неразрешимость возникает уже для экзистенциальных предложений PA из-за отрицательного ответа на десятую проблему Гильберта , доказательство которой подразумевает, что все вычислимо перечислимые множества являются диофантовыми множествами и, следовательно, могут быть определены с помощью экзистенциально квантифицированных формул (со свободными переменными) PA . Формулы ПА с более высоким кванторным рангом (большее количество чередований кванторов), чем формулы существования, более выразительны и определяют множества на более высоких уровнях арифметической иерархии .

Нестандартные модели

Хотя обычные натуральные числа удовлетворяют аксиомам PA, существуют и другие модели (называемые « нестандартными моделями »); из теоремы компактности следует , что существование нестандартных элементов не может быть исключено в логике первого порядка. ^[27] Восходящая теорема Левенхайма–Скулема показывает, что существуют нестандартные модели PA всех бесконечных мощностей. Это не относится к исходным аксиомам Пеано (второго порядка), которые имеют только одну модель с точностью до изоморфизма. ^[28] Это иллюстрирует один из способов, почему система PA первого порядка слабее, чем аксиомы Пеано второго порядка.

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

Естественно задаться вопросом, можно ли явно построить счетную нестандартную модель. Ответ утвердительный, поскольку Сколем в 1933 году предоставил явную конструкцию такой нестандартной модели . С другой стороны, теорема Тенненбаума , доказанная в 1959 году, показывает, что не существует счетной нестандартной модели ПА, в которой вычислима операция сложения или умножения . ^[29] Этот результат показывает, что трудно быть полностью явным при описании операций сложения и умножения счетной нестандартной модели PA. Существует только один возможный тип заказа счетной нестандартной модели. Полагая , что ω — тип порядка натуральных чисел, ζ — тип порядка целых чисел, а η — тип порядка рациональных чисел, тип порядка любой счетной нестандартной модели PA равен ω + ζ · η , что может быть визуализируется как копия натуральных чисел, за которой следует плотный линейный порядок копий целых чисел.

Перелив

Разрез в нестандартной модели M — это непустое подмножество C в M , так что C замкнуто вниз ( x < y и y ∈ C ⇒ x ∈ C ), а C замкнуто относительно преемника. Правильный разрез — это разрез , который является правильным подмножеством M. Каждая нестандартная модель имеет множество правильных разрезов, в том числе тот, который соответствует стандартным натуральным числам. Однако схема индукции в арифметике Пеано не позволяет определить какой-либо правильный разрез. Лемма о переливе, впервые доказанная Абрахамом Робинсоном, формализует этот факт.

Лемма о перерасходе ^[30]  —  Пусть M — нестандартная модель PA, и пусть C — собственный разрез M . Предположим, что это кортеж элементов M и формула на языке арифметики так, что ${\displaystyle {\bar {a}}}$ ${\displaystyle \phi (x,{\bar {a}})}$

${\displaystyle M\vDash \phi (b,{\bar {a}})}$для всех b ∈ C.

Тогда в M существует элемент c , больший любого элемента C, такой, что

${\displaystyle M\vDash \phi (c,{\bar {a}}).}$

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

• Философский портал
• Математический портал

• Основы математики
• Теорема Фреге
• Теорема Гудштейна
• Неологизм
• Нестандартная модель арифметики
• Теорема Пэрис – Харрингтона
• Арифметика Пресбургера
• арифметика Робинсона
• Арифметика второго порядка
• Типографская теория чисел

Примечания

1. ближайший световой фрагмент, соответствующий 0, и соседний фрагмент, соответствующий преемнику
2. Несмежный набор удовлетворяет аксиоме 1, поскольку он имеет элемент 0, 2–5, поскольку он не влияет на отношения равенства, 6 и 8, поскольку все части имеют преемника, за исключением нулевого элемента, и аксиоме 7, поскольку никакие два домино не опрокидываются. или опрокинуты одним и тем же куском.
3. " " можно доказать на основе других аксиом (в логике первого порядка) следующим образом. Во-первых, по дистрибутивности и аддитивному тождеству. Во-вторых, по аксиоме 15. Если тогда добавлением того же элемента и коммутативности, а значит , и заменой, противоречащей иррефлексивности. Поэтому должно быть так . ${\displaystyle \forall x\ (x\cdot 0=0)}$ ${\displaystyle x\cdot 0+x\cdot 0=x\cdot (0+0)=x\cdot 0=x\cdot 0+0}$ ${\displaystyle x\cdot 0=0\lor x\cdot 0>0}$ ${\displaystyle x\cdot 0>0}$ ${\displaystyle x\cdot 0+x\cdot 0>x\cdot 0+0}$ ${\displaystyle x\cdot 0+0>x\cdot 0+0}$ ${\displaystyle x\cdot 0=0}$

Рекомендации

Цитаты

1. "Пеано". Полный словарь Random House Webster .
2. Грассманн 1861.
3. Wang 1957, стр. 145, 147, «По собственному признанию Пеано довольно хорошо известно, что Пеано […] широко использовал работы Грассмана в своей разработке аксиом. Не так хорошо известно, что Грассман по сути, имела характеристику множества всех целых чисел, теперь общепринятую в текстах современной алгебры, что оно образует упорядоченную область целостности , в которой каждый набор положительных элементов имеет наименьший член. […] [Книга Грассмана], вероятно, была первой серьезной и довольно успешная попытка поставить цифры на более или менее аксиоматическую основу».
4. Пирс 1881.
5. Шилдс 1997.
6. Ван Хейеноорт 1967, с. 94.
7. Ван Хейеноорт 1967, с. 2.
8. Ван Хейеноорт 1967, с. 83.
9. Пеано 1889, с. 1.
10. Пеано 1908, с. 27.
11. Мэтт ДеВос, математическая индукция, Университет Саймона Фрейзера
12. Херардо кон Диас, Математическая индукция. Архивировано 2 мая 2013 г. в Wayback Machine , Гарвардский университет.
13. Meseguer & Goguen 1986, разделы 2.3 (стр. 464) и 4.1 (стр. 471).
14. Суппес 1960, Хэтчер 2014
15. Тарский и Гивант 1987, раздел 7.6.
16. Фриц 1952, с. 137
    Иллюстрацией «интерпретации» является собственное определение «кардинального числа», данное Расселом. Неинтерпретируемой системой в данном случае являются аксиомы Пеано для системы счисления, трех примитивных идей и пяти аксиом которых, как считал Пеано, было достаточно, чтобы можно было вывести все свойства системы натуральных чисел. На самом деле, утверждает Рассел, аксиомы Пеано определяют любую прогрессию формы , одним из примеров которой является ряд натуральных чисел. ${\displaystyle x_{0},x_{1},x_{2},\ldots ,x_{n},\ldots }$
17. Грей 2013, с. 133
    Поэтому Пуанкаре обратился к вопросу, может ли логицизм порождать арифметику, точнее, арифметику порядковых чисел. Кутюра, сказал Пуанкаре, принял аксиомы Пеано как определение числа. Но это не годится. Невозможно показать, что аксиомы свободны от противоречий, найдя их примеры, и любая попытка показать, что они свободны от противоречий, исследуя всю совокупность их следствий, потребовала бы самого принципа математической индукции, который, по мнению Кутюра, они подразумевали. Ибо (в дальнейшем отрывке, исключенном из Сан-Демократической школы) либо кто-то принял этот принцип, чтобы доказать его, что доказывало бы только то, что, если он истинен, он не противоречит самому себе, а это ни о чем не говорит; или кто-то использовал принцип в другой форме, чем изложенная, и в этом случае нужно было показать, что число шагов в рассуждении было целым числом согласно новому определению, но это было невозможно сделать (1905c, 834).
18. Гильберт 1902.
19. Гёдель 1931.
20. Гёдель 1958 г.
21. Генцен 1936 г.
22. Уиллард 2001.
23. Парти, Тер Меулен и Уолл 2012, стр. 215.
24. Харсаньи (1983).
25. Мендельсон 1997, с. 155.
26. Кэй 1991, стр. 16–18.
27. Гермес 1973, VI.4.3, представляющий теорему Торальфа Скулема.
28. Гермес 1973, VI.3.1.
29. Кэй 1991, раздел 11.3.
30. Кэй 1991, стр. 70 и далее..

Источники

• Дэвис, Мартин (1974). Вычислимость. Заметки Барри Джейкобса . Курантовский институт математических наук Нью -Йоркского университета .

• Дедекинд, Ричард (1888). Был ли Sind и Sollen die Zahlen? [ Какие и какими должны быть цифры? ] (PDF) . Посмотретьег . Проверено 4 июля 2016 г.
  • Два английских перевода:
    • Беман, Вустер, Вудрафф (1901). Очерки теории чисел (PDF) . Дуврские публикации .{{cite book}}: CS1 maint: multiple names: authors list (link)
    • Эвальд, Уильям Б. (1996). От Канта до Гильберта: Справочник по основам математики. Издательство Оксфордского университета . стр. 787–832. ISBN 978-0-19-853271-2.

• Фриц, Чарльз А. младший (1952). Конструкция внешнего мира Бертрана Рассела . Нью-Йорк, Humanities Press.

• Генцен, Герхард (1936). Перепечатано в английском переводе в его Собрании сочинений 1969 г. М. Е. Сабо, изд. «Die Widerspruchsfreiheit der Reinen Zahlentheorie». Математические Аннален . 112 : 132–213. дои : 10.1007/bf01565428. S2CID  122719892.

• Гёдель, Курт (1931). Подробности о английских переводах см. в разделе «О формально неразрешимых предложениях Principia Mathematica и родственных систем» . «Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I» (PDF) . Монашефте по математике . 38 : 173–198. дои : 10.1007/bf01700692. S2CID  197663120. Архивировано из оригинала (PDF) 11 апреля 2018 г. Проверено 31 октября 2013 г.

• Гёдель, Курт (1958). Перепечатано в английском переводе в 1990 году. Собрание сочинений Гёделя , Том II. Соломон Феферман и др., ред. «Über eine bisher noch nicht benützte Erweiterung des Finin Standpunktes». Диалектика . Издательство Оксфордского университета . 12 (3–4): 280–287. дои : 10.1111/j.1746-8361.1958.tb01464.x .

• Грассманн, Герман Гюнтер (1861). Lehrbuch der Arithmetik für höhere Lehranstalten. Верлаг фон Теод. Хр. о. Энслин.

• Грей, Джереми (2013). «Эссеист». Анри Пуанкаре: Научная биография . Издательство Принстонского университета . п. 133. ИСБН 978-0-691-15271-4.

• Харсаньи, Джон К. (1983). «Математика, эмпирические факты и логическая необходимость». В Хемпеле, Карл Г.; Патнэм, Хилари; Эсслер, Вильгельм К. (ред.). Методология, эпистемология и философия науки . стр. 167–192. дои : 10.1007/978-94-015-7676-5_8. ISBN 978-90-481-8389-0. S2CID  121297669.

• Хэтчер, Уильям С. (2014) [1982]. Логические основы математики. Эльзевир. ISBN 978-1-4831-8963-5.Выводит аксиомы Пеано (называемые S ) из нескольких аксиоматических теорий множеств и из теории категорий .

• Гермес, Ганс (1973). Введение в математическую логику . Hochschultext. Спрингер. ISBN 3-540-05819-2. ISSN  1431-4657.

• Гильберт, Дэвид (1902). Перевод Винтона, Мэйби. «Mathematische Issuee» [Математические задачи]. Бюллетень Американского математического общества . 8 (10): 437–479. дои : 10.1090/s0002-9904-1902-00923-3 .

• Кэй, Ричард (1991). Модели арифметики Пеано . Издательство Оксфордского университета . ISBN 0-19-853213-Х.

• Ландау, Эдмунд (1965). Основной анализ . Выводит основные системы счисления из аксиом Пеано. Английский/немецкий словарь включен. Издательство AMS Челси . ISBN 978-0-8284-0141-8.

• Мендельсон, Эллиотт (декабрь 1997 г.) [декабрь 1979 г.]. Введение в математическую логику (дискретная математика и ее приложения) (4-е изд.). Спрингер. ISBN 978-0-412-80830-2.

• Месегер, Хосе; Гоген, Джозеф А. (декабрь 1986 г.). «Инициальность, индукция и вычислимость». У Мориса Нивата и Джона К. Рейнольдса (ред.). Алгебраические методы в семантике (PDF) . Кембридж: Издательство Кембриджского университета. стр. 459–541. ISBN 978-0-521-26793-9.

• Парти, Барбара; Тер Меулен, Алиса ; Уолл, Роберт (2012). Математические методы в лингвистике. Спрингер. ISBN 978-94-009-2213-6.

• Пеано, Джузеппе (1908). Formulario Mathematico (V-ред.). Турин, Бокка Фрер, Гл. Клаузен. п. 27.

• Пирс, CS (1881). «О логике числа». Американский журнал математики . 4 (1): 85–95. дои : 10.2307/2369151. JSTOR  2369151. MR  1507856.

• Шилдс, Пол (1997). «3. Аксиоматизация арифметики Пирса». В Хаузере, Натан; Робертс, Дон Д.; Ван Эвра, Джеймс (ред.). Исследования по логике Чарльза Сандерса Пирса . Издательство Университета Индианы. стр. 43–52. ISBN 0-253-33020-3.

• Суппес, Патрик (1960). Аксиоматическая теория множеств . Дуврские публикации . ISBN 0-486-61630-4.Выводит аксиомы Пеано из ZFC.

• Тарский, Альфред ; Гивант, Стивен (1987). Формализация теории множеств без переменных . Публикации коллоквиума AMS. Том. 41. Американское математическое общество . ISBN 978-0-8218-1041-5.

• Ван Хейеноорт, Жан (1967). От Фреге до Геделя: Справочник по математической логике, 1879–1931 . Издательство Гарвардского университета. ISBN 978-0-674-32449-7.
  • Содержит переводы следующих двух статей с ценными комментариями:
    • Дедекинд, Ричард (1890). Письмо Кеферштейну . На стр. 100, он переформулирует и защищает свои аксиомы 1888 года. стр. 98–103.
    • Пеано, Джузеппе (1889). Arithmetices principia, nova Methodo Exposita [ Принципы арифметики, представленные новым методом ]. Отрывок из трактата, в котором Пеано впервые представил свои аксиомы и рекурсивно определил арифметические операции. Братья Бокка. стр. 83–97.

• Ван Остен, Яап (июнь 1999 г.). «Введение в арифметику Пеано (неполнота Гёделя и нестандартные модели)» (PDF) . Утрехтский университет . Проверено 2 сентября 2023 г.

• Ван, Хао (июнь 1957 г.). «Аксиоматизация арифметики». Журнал символической логики . Ассоциация символической логики . 22 (2): 145–158. дои : 10.2307/2964176. JSTOR  2964176. S2CID  26896458.

• Уиллард, Дэн Э. (2001). «Самопроверяющиеся системы аксиом, теорема о неполноте и связанные с ней принципы отражения» (PDF) . Журнал символической логики . 66 (2): 536–596. дои : 10.2307/2695030. JSTOR  2695030. MR  1833464. S2CID  2822314.

дальнейшее чтение

• Басс, Сэмюэл Р. (1998). «Глава II: Теория доказательства первого порядка арифметики». В Бассе, Сэмюэл Р. (ред.). Справочник по теории доказательств . Нью-Йорк: Elsevier Science. ISBN 978-0-444-89840-1.

• Мендельсон, Эллиотт (июнь 2015 г.) [декабрь 1979 г.]. Введение в математическую логику (дискретная математика и ее приложения) (6-е изд.). Чепмен и Холл/CRC. ISBN 978-1-4822-3772-6.

• Смуллян, Раймонд М. (декабрь 2013 г.). Книга гёделевских головоломок: загадки, парадоксы и доказательства. Дуврские публикации. ISBN 978-0-486-49705-1.

• Такеути, Гаиси (2013). Теория доказательств (Второе изд.). Минеола, Нью-Йорк. ISBN 978-0-486-49073-1.{{cite book}}: CS1 maint: location missing publisher (link)

Внешние ссылки

• Мурзи, Мауро. «Анри Пуанкаре». Интернет-энциклопедия философии .Включает обсуждение критики Пуанкаре аксиом Пеано.
• Подниекс, Карлис (25 января 2015 г.). «3. Арифметика первого порядка». Что такое математика: теорема Гёделя и ее окрестности. стр. 93–121.
• «Аксиомы Пеано», Математическая энциклопедия , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. «Аксиомы Пеано». Математический мир .
• Беррис, Стэнли Н. (2001). «Что такое числа и в чем их значение?: Дедекинд».Комментарий к творчеству Дедекинда.

Эта статья включает в себя материалы от PA на PlanetMath , которые доступны под лицензией Creative Commons Attribution/Share-Alike License .