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

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

Аксиоматизация , арифметики обеспечиваемая аксиомами Пеано , обычно называется арифметикой Пеано .

Важность формализации арифметики не была оценена должным образом до работы Германа Грассмана , который показал в 1860-х годах, что многие факты в арифметике могут быть получены из более фундаментальных фактов о последующих операциях и индукции . В 1881 году Чарльз Сандерс Пирс представил аксиоматизацию арифметики натуральных чисел. В 1888 году Рихард Дедекинд предложил еще одну аксиоматизацию арифметики натуральных чисел, а в 1889 году Пеано опубликовал упрощенную версию их в виде сборника аксиом в своей книге «Принципы арифметики, представленные новым методом» ( лат .: Arithmetices principia, nova Methodo). экспозиция ).

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

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

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

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

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

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

В исходной формулировке аксиом Пеано в качестве «первого» натурального числа использовалась 1 вместо 0. в то время как аксиомы в Formulario mathematico включают ноль.

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

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. Для каждого натурального числа S n ( n ) = 0 неверно. То есть не существует натурального числа, преемником которого был бы 0.

Цепочка светлых домино справа, начиная с ближайшего, может обозначать множество N натуральных чисел. Однако аксиомам 1–8 также удовлетворяет набор всех домино — светлых или темных — вместе взятых. 9-я аксиома ( индукция ) ограничивает N цепочкой из легких фигур («никакого мусора»), поскольку при падении ближайшей из них упадут только легкие домино.

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

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

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

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

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

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

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

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

Добавление

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

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

Например:

${\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}}$

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

Умножение

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

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

Это легко увидеть $S(0)$ является мультипликативным правым тождеством :

$a\cdot S(0)=a+(a\cdot 0)=a+0=a$

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

• $S(0)$ является левой идентичностью 0: $S(0)\cdot 0=0$.
• Если $S(0)$ является левым тождеством $a$ (то есть $S(0)\cdot a=a$), затем $S(0)$ также является левой идентичностью $S(a)$: $S(0)\cdot S(a)=S(0)+S(0)\cdot a=S(0)+a=a+S(0)=S(a+0)=S(a)$, используя коммутативность сложения.

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

$a\cdot (b+c)=(a\cdot b)+(a\cdot c)$.

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

Неравенства

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

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

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

• 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 , должно быть так, что ∉ X. 0
• что для любого 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, удовлетворяющий

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

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

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

Основная статья: Теоретико-множественное определение натуральных чисел

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

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

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

${\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 удовлетворяет аксиомам Пеано.

Арифметика Пеано равносовместима с несколькими слабыми системами теории множеств. Одной из таких систем является 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 1} ( C ) имеет начальный объект; этот исходный объект известен как натурального числа в C. объект Если ( N , 0, S ) — этот исходный объект, а ( X , 0 _X , S _X ) — любой другой объект, то уникальное отображение u : ( N , 0, S ) → ( X , 0 _X , S _X ) таков, что

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

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

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

Дополнительная информация: вторая проблема Гильберта и непротиворечивость.

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

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

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

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

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

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

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

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

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

$\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 )}$

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

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

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

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

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

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

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

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

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

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

Основная статья: Нестандартная модель арифметики

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

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

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

переиграть

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

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

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

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

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

См. также

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

Ссылки

Источники

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

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

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

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

• Гёдель, Курт (1931). «О формально неразрешимых теоремах Principia Mathematica и родственных систем I» (PDF) . Ежемесячные журналы по математике . 38 . Подробную информацию об английских переводах см . в разделе «О формально неразрешимых предложениях Principia Mathematica и родственных систем» : 173–198. дои : 10.1007/bf01700692 . S2CID   197663120 . Архивировано из оригинала (PDF) 11 апреля 2018 г. Проверено 31 октября 2013 г.

• Гёдель, Курт (1958). «О неиспользованном до сих пор расширении конечной точки зрения» . Диалектика . 12 (3-4). Гёделя Переиздано в английском переводе в 1990 году. Собрание сочинений , Том II, Соломон Феферман и др., ред. Издательство Оксфордского университета : 280–287. дои : 10.1111/j.1746-8361.1958.tb01464.x .

• Грассманн, Герман Гюнтер (1861). Учебник арифметики для высших учебных заведений . Издатель Теод. Хр. миссис Энслин.

• Грей, Джереми (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). « Математические проблемы». Бюллетень Американского математического общества . 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). Математический формуляр (5-е изд.). Турин, Bocca frères, Ch. Клаузен п. 27.

• Пирс, CS (1881). «О логике числа» . Американский журнал математики . 4 (1): 85–95. дои : 10.2307/2369151 . JSTOR   2369151 . МР   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 . МР   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: отсутствует местоположение издателя ( ссылка )

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

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

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