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

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

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

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

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

Девять аксиом Пеано содержат три типа утверждений. Первая аксиома утверждает существование по крайней мере одного члена множества натуральных чисел. Следующие четыре являются общими утверждениями о равенстве ; в современных трактовках они часто не рассматриваются как часть аксиом Пеано, а скорее как аксиомы «базовой логики». ^[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 0+b=b}$ ${\displaystyle S(a)+b=S(a+b)}$ ${\displaystyle b}$ ${\displaystyle a+b=b+a}$ ${\displaystyle b}$

Умножение

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

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

Следовательно, по аксиоме индукции является мультипликативной левой единицей всех натуральных чисел. Более того, можно показать ^[14] , что умножение коммутативно и распределяется относительно сложения: ${\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} }$

• а + с ≤ b + с , и
• а · с ≤ б · с .

Таким образом, структура ( 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 , 0A _, SA ) _и ( NB , 0B _, SB ) _, то существует единственный гомоморфизм f  : NA → _{NB , удовлетворяющий}

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

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

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

Аксиомы Пеано могут быть выведены из теоретико-множественных конструкций натуральных чисел и аксиом теории множеств, таких как ZF . ^[15] Стандартная конструкция натуральных чисел, предложенная Джоном фон Нейманом , начинается с определения 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 удовлетворяет аксиомам Пеано.

Арифметика Пеано равносогласована с несколькими слабыми системами теории множеств. ^[16] Одной из таких систем является 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 .

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

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

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

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

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

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

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

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

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

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

Вышеуказанная аксиоматизация арифметики Пеано использует сигнатуру, которая имеет только символы для нуля, а также для операций наследования, сложения и умножения. Существует много других различных, но эквивалентных аксиоматизаций. Одна из таких альтернатив ^[27] использует символ отношения порядка вместо операции наследования и язык дискретно упорядоченных полуколец (аксиомы 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 получается путем добавления схемы индукции первого порядка.

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

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

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

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

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

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

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

Перелив

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

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

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

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

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

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

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

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

Примечания

1. ближайшая легкая часть, соответствующая 0, и соседняя часть, соответствующая последующему элементу
2. Несмежный набор удовлетворяет аксиоме 1, поскольку он содержит нулевой элемент, аксиомам 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 .
2. Грассман 1861.
3. Ван 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. Формальные доказательства см., например, в Файл:Индуктивные доказательства свойств сложения, умножения из рекурсивных определений.pdf .
15. Саппс 1960, Хэтчер 2014
16. Тарский и Гивант 1987, раздел 7.6.
17. Фриц 1952, стр. 137
    Иллюстрацией «интерпретации» является собственное определение Рассела «кардинального числа». Неинтерпретируемая система в этом случае — это аксиомы Пеано для числовой системы, три примитивные идеи и пять аксиом которых, как считал Пеано, были достаточны для того, чтобы вывести все свойства системы натуральных чисел. На самом деле, утверждает Рассел, аксиомы Пеано определяют любую прогрессию формы, одним из примеров которой является ряд натуральных чисел. ${\displaystyle x_{0},x_{1},x_{2},\ldots ,x_{n},\ldots }$
18. Gray 2013, стр. 133
    Итак, Пуанкаре обратился к вопросу, может ли логицизм породить арифметику, точнее, арифметику ординалов. Кутюра, сказал Пуанкаре, принял аксиомы Пеано как определение числа. Но этого не будет. Аксиомы не могут быть показаны свободными от противоречий путем нахождения их примеров, и любая попытка показать, что они свободны от противоречий, исследуя совокупность их импликаций, потребовала бы самого принципа математической индукции, который, как полагал Кутюра, они подразумевали. Ибо (в дальнейшем отрывке, выпавшем из S&M) либо один предполагал принцип, чтобы доказать его, что доказывало бы только то, что если он истинен, то он не является внутренне противоречивым, что ничего не говорит; или же принцип использовался в иной форме, чем та, которая была заявлена, и в этом случае нужно было показать, что число шагов в рассуждениях было целым числом согласно новому определению, но сделать это было невозможно (1905c, 834).
19. Гильберт 1902.
20. Гёдель 1931.
21. Гёдель 1958
22. Генцен 1936
23. Уиллард 2001.
24. Парти, Тер Мейлен и Уолл 2012, стр. 215.
25. Харсани (1983).
26. Мендельсон 1997, стр. 155.
27. Кей 1991, стр. 16–18.
28. Гермес 1973, VI.4.3, представляющий теорему Торальфа Скулема.
29. Гермес 1973, VI.3.1.
30. Кей 1991, Раздел 11.3.
31. Кей 1991, стр. 70 и далее.

Источники

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

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

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

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

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

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

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

• Грей, Джереми (2013). «Эссеист». Анри Пуанкаре: Научная биография . Princeton University Press . стр. 133. ISBN 978-0-691-15271-4.

• Harsanyi, John C. (1983). «Математика, эмпирические факты и логическая необходимость». В Hempel, Carl G.; Putnam, Hilary; Essler, Wilhelm K. (ред.). Методология, эпистемология и философия науки . стр. 167–192. doi :10.1007/978-94-015-7676-5_8. ISBN 978-90-481-8389-0. S2CID  121297669.

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

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

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

• Кей, Ричард (1991). Модели арифметики Пеано . Oxford University Press . ISBN 0-19-853213-X.

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

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

• Meseguer, José; Goguen, Joseph A. (декабрь 1986 г.). «Initiality, induction, and computability». В Морисе Нива и Джоне К. Рейнольдсе (ред.). Algebraic Methods in Semantics (PDF) . Кембридж: Cambridge University Press. стр. 459–541. ISBN 978-0-521-26793-9.

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

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

• Пирс, К. С. (1881). «О логике чисел». American Journal of Mathematics . 4 (1): 85–95. doi :10.2307/2369151. JSTOR  2369151. MR  1507856.

• Shields, Paul (1997). "3. Аксиоматизация арифметики Пирса". В Houser, Nathan; Roberts, Don D.; Van Evra, James (ред.). Исследования по логике Чарльза Сандерса Пирса . Indiana University Press. стр. 43–52. ISBN 0-253-33020-3.

• Suppes, Patrick (1960). Аксиоматическая теория множеств . Dover Publications . 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 [ Принципы арифметики, изложенные новым методом ]. Отрывок из трактата, в котором Пеано впервые представил свои аксиомы и рекурсивно определил арифметические операции. Fratres Bocca. С. 83–97.

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

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

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

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

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

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

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

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

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

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

В данной статье использованы материалы PA on PlanetMath , лицензированные по лицензии Creative Commons Attribution/Share-Alike License .