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

В математической логике аксиомы Пеано, также известные как аксиомы Дедекинда – Пеано или постулаты Пеано, являются аксиомами для натуральных чисел, представленных 19 век итальянский математик Джузеппе Пеано. Эти аксиомы использовались почти без изменений в ряде метаматематических исследований, включая исследования фундаментальных вопросов о том, непротиворечива и завершена теория чисел.>Необходимость формализовать арифметику не была хорошо оценена до работы Германа Грассмана, который показал в 1860-х годах, что многие арифметические факты могут быть получены из более основных фактов о последующая операция и индукция. В 1881 году Чарльз Сандерс Пирс представил аксиоматизацию арифметики натуральных чисел. В 1888 году Ричард Дедекинд предложил другую аксиоматизацию арифметики с натуральными числами, а в 1889 году Пеано опубликовал их упрощенную версию в виде собрания аксиом в своей книге Принципы арифметики, представленные А. новый метод (латинское : Принципы арифметики, nova methoddo exposita).

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

Содержание

• 1 Формулировка
• 2 Арифметика
  • 2.1 Сложение
  • 2.2 Умножение
  • 2.3 Неравенства
• 3 Теория арифметики первого порядка
  • 3.1 Эквивалентные аксиоматизации
• 4 Модели
  • 4.1 Теоретико-множественные модели
  • 4.2 Интерпретация в теории категорий
• 5 Нестандартные модели
  • 5.1 Излишек
• 6 Согласованность
• 7 См. Также
• 8 Примечания
• 9 Ссылки
  • 9.1 Цитаты
  • 9.2 Источники
• 10 Дополнительная литература
• 11 Внешние ссылки

Формулировка

Когда Пеано сформулировал свои аксиомы, язык математической логики находился в своем младенчество. Система логической нотации, которую он создал для представления аксиом, не оказалась популярной, хотя она была зародышем современной нотации для членства в множестве (∈, которое происходит от ε Пеано) и импликации. (⊃, происходящее от перевернутой буквы «C» Пеано.) Пеано проводил четкое различие между математическими и логическими символами, которое еще не было распространено в математике; такое разделение было впервые введено в Begriffsschrift Gottlob Frege, опубликованном в 1879 году. Пеано не знал о работе Фреге и независимо воссоздал свой логический аппарат на основе работы Логические и Шредер.

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

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

1. 0 является натуральным числом.

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

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

Первоначальная формулировка аксиом Пеано использовал 1 вместо 0 в качестве «первого» натурального числа. Этот выбор является произвольным, так как эти аксиомы не наделяют константу 0 какими-либо дополнительными свойствами. Однако, поскольку 0 является аддитивным тождеством в арифметике, большинство современных формулировок аксиом Пеано начинаются с 0.

Аксиомы 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 ) с другим. Он определяется рекурсивно как:

$a\; +\; 0\; =\; a,\; (1)\; a\; +\; S\; (b)\; =\; S\; (a\; +\; b).\; (2)\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; a\; +\; 0\; =\; a,\; \{\backslash \; textrm\; \{(1)\}\}\; \backslash \backslash \; a\; +\; S\; (b)\; =\; S\; (a\; +\; b).\; \{\backslash \; Textrm\; \{\; (2)\}\}\; \backslash \; end\; \{align\}\}\}$

Например:

$a\; +\; 1\; =\; a\; +\; S\; (0)\; по\; определению\; =\; S\; (a\; +\; 0)\; с\; использованием\; (2)\; =\; S\; (a),\; используя\; (1)\; a\; +\; 2\; =\; a\; +\; S\; (1)\; по\; определению\; =\; S\; (a\; +\; 1)\; используя\; (2)\; =\; S\; (S\; (a))\; используя\; a\; +\; 1\; =\; S\; (a)\; a\; +\; 3\; =\; a\; +\; S\; (2)\; по\; определению\; =\; S\; (a\; +\; 2),\; используя\; (2)\; =\; S\; (S\; (S\; (a))),\; используя\; a\; +\; 2\; =\; S\; (S\; (a))\; и\; т.\; Д.\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\; \}\; a\; +\; 1\; =\; a\; +\; S\; (0)\; \{\backslash \; t\_dv\; \{по\; определению\}\}\; \backslash \backslash \; =\; S\; (a\; +\; 0)\; \{\backslash \; t\_dv\; \{using\; (2)\}\}\; \backslash \backslash \; =\; S\; (a),\; \{\backslash \; t\_dv\; \{с\; использованием\; (1)\}\}\; \backslash \backslash \backslash \backslash \; a\; +\; 2\; =\; a\; +\; S\; (1)\; \{\backslash \; t\_dv\; \{по\; определению\}\}\; \backslash \backslash \; =\; S\; (a\; +\; 1)\; \{\backslash \; t\_dv\; \{с\; использованием\; (2)\}\}\; \backslash \backslash \; =\; S\; (S\; (a))\; \{\backslash \; t\_dv\; \{using\}\}\; a\; +\; 1\; =\; S\; (a)\; \backslash \backslash \backslash \backslash \; a\; +\; 3\; =\; a\; +\; S\; (2)\; \{\backslash \; t\_dv\; \{по\; определению\}\}\; \backslash \backslash \; =\; S\; (a\; +\; 2)\; \{\backslash \; t\_dv\; \{using\; (2)\}\}\; \backslash \backslash \; =\; S\; (S\; (S\; (a)))\; \{\backslash \; t\_dv\; \{using\}\}\; a\; +\; 2\; =\; S\; (S\; (a))\; \backslash \backslash \; \{\backslash \; text\; \{etc.\}\}\; \backslash \backslash \backslash \; end\; \{align\}\}\}$

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

Умножение

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

$a\; \cdot \; 0\; =\; 0,\; a\; \cdot \; S\; (b)\; =\; a\; +\; (a\; \cdot \; b).\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; a\; \backslash \; cdot\; 0\; =\; 0,\; \backslash \backslash \; a\; \backslash \; cdot\; S\; (b)\; =\; a\; +\; (a\; \backslash \; cdot\; b).\; \backslash \; end\; \{align\}\}\}$

Легко видеть что S (0) (или "1" на знакомом языке десятичного представления ) является мультипликативным правым тождеством :

a · S (0) = a + (a · 0) = a + 0 = a

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

• S (0) является левым тождеством 0: S ( 0) · 0 = 0.
• Если S (0) - левая единица a (то есть S (0) · a = a), то S (0) также является левой единицей S ( а): S (0) · S (a) = S (0) + S (0) · a = S (0) + a = a + S (0) = S (a + 0) = S (a).

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

a · (b + c) = (a · b) + (a · c).

Таким образом, (N, +, 0, ·, S (0)) - коммутативное полукольцо.

Неравенства

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

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

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

• a + c ≤ b + c, и
• a · c ≤ b · c.

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

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

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

• φ (0) истинно, и
• для любого n, k ∈ N, если k ≤ n влечет, что φ (k) истинно, то φ (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 имеет наименьший элемент.

Теория арифметики первого порядка

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

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

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

• $\forall \; x\; (\; 0\; \ne \; S\; (x))\; \{\backslash \; displaystyle\; \backslash \; forall\; x\; \backslash \; (0\; \backslash \; neq\; S\; (x))\}$
• $\forall \; x,\; y\; (S\; (x)\; =\; S\; (y)\; \Rightarrow \; x\; =\; y)\; \{\backslash \; displaystyle\; \backslash \; для\; всех\; x,\; y\; \backslash \; (S\; (x)\; =\; S\; (y)\; \backslash \; Rightarrow\; x\; =\; y)\}$
• $\forall \; x\; (x\; +\; 0\; =\; x)\; \{\backslash \; displaystyle\; \backslash \; forall\; x\; \backslash \; (x\; +\; 0\; =\; x)\}$
• $\forall \; Икс,\; Y\; (Икс\; +\; S\; (Y)\; =\; S\; (X\; +\; Y))\; \{\backslash \; Displaystyle\; \backslash \; forall\; x,\; y\; \backslash \; (x\; +\; S\; (y)\; =\; S\; (x\; +\; y))\}$
• $\forall \; Икс\; (Икс\; \cdot \; 0\; знак\; равно\; 0)\; \{\backslash \; Displaystyle\; \backslash \; forall\; x\; \backslash \; (x\; \backslash \; cdot\; 0\; =\; 0)\}$
• $\forall \; x,\; y\; (x\; \cdot \; S\; (y)\; =\; x\; \cdot \; y\; +\; x)\; \{\backslash \; displaystyle\; \backslash \; forall\; x,\; y\; \backslash \; (x\; \backslash \; cdot\; S\; (y)\; =\; x\; \backslash \; cdot\; y\; +\; x)\}$

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

$\forall \; y\; ¯\; ((\phi \; (0,\; y\; ¯)\; \wedge \; \forall \; x\; (\phi \; (x,\; y\; ¯)\; \Rightarrow \; \phi \; (S\; (x),\; y\; ¯)))\; \Rightarrow \; x\; \phi \; (x,\; y\; ¯))\; \{\backslash \; displaystyle\; \backslash \; forall\; \{\backslash \; bar\; \{y\}\}\; ((\backslash \; varphi\; (0,\; \{\backslash \; bar\; \{y\}\})\; \backslash \; land\; \backslash \; forall\; x\; (\backslash \; varphi\; (x,\; \{\backslash \; bar\; \{y\}\})\; \backslash )\; Rightarrow\; \backslash \; varphi\; (S\; (x),\; \{\backslash \; bar\; \{y\}\})))\; \backslash \; Rightarrow\; \backslash \; forall\; x\; \backslash \; varphi\; (x,\; \{\backslash \; bar\; \{y\}\}))\}$

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

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

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

1. $\forall \; x,\; y,\; z\; ((x\; +\; y)\; +\; z\; =\; x\; +\; (y\; +\; z))\; \{\backslash \; displaystyle\; \backslash \; forall\; x,\; y,\; z\; \backslash \; ((x\; +\; y)\; +\; z\; =\; x\; +\; (y\; +\; z))\}$, т.е. сложение является ассоциативным.
2. $\forall \; x,\; y\; (x\; +\; y\; =\; y\; +\; x)\; \{\backslash \; displaystyle\; \backslash \; forall\; x,\; y\; \backslash \; (x\; +\; y\; =\; y\; +\; x)\}$, т. е. сложение коммутативное.
3. $\forall \; x,\; y,\; z\; ((x\; \cdot \; y)\; \cdot \; Z\; знак\; равно\; Икс\; \cdot \; (Y\; \cdot \; Z))\; \{\backslash \; Displaystyle\; \backslash \; forall\; x,\; y,\; z\; \backslash \; ((x\; \backslash \; cdot\; y)\; \backslash \; cdot\; z\; =\; x\; \backslash \; cdot\; (y\; \backslash \; cdot\; z))\}$, т.е. умножение является ассоциативным.
4. $\forall \; x,\; y\; (x\; \cdot \; y\; =\; y\; \cdot \; x)\; \{\backslash \; displaystyle\; \backslash \; forall\; x,\; y\; \backslash \; (x\; \backslash \; cdot\; y\; =\; y\; \backslash \; cdot\; x)\}$, т.е. умножение коммутативно.
5. $\forall \; x,\; y,\; z\; (x\; \cdot \; (y\; +\; z)\; =\; (x\; \cdot \; y)\; +\; (x\; \cdot \; z))\; \{\backslash \; displaystyle\; \backslash \; forall\; x,\; y,\; z\; \backslash \; (x\; \backslash \; cdot\; (y\; +\; z)\; =\; (x\; \backslash \; cdot\; y)\; +\; (x\; \backslash \; cdot\; z))\}$, т.е. умножение распределяет над сложением.
6. $\forall \; x\; (x\; +\; 0\; знак\; равно\; x\; \wedge \; x\; \cdot \; 0\; =\; 0)\; \{\backslash \; displaystyle\; \backslash \; forall\; x\; \backslash \; (x\; +\; 0\; =\; x\; \backslash \; land\; x\; \backslash \; cdot\; 0\; =\; 0)\}$, т. Е. Ноль - это тождество для сложения, а n поглощающий элемент для умножения (фактически лишний).
7. $\forall \; x\; (x\; \cdot \; 1\; =\; x)\; \{\backslash \; displaystyle\; \backslash \; forall\; x\; \backslash \; (x\; \backslash \; cdot\; 1\; =\; x)\}$, т. е. единица является тождеством для умножения.
8. , то есть '<' operator is транзитивный.
9. , т. е. оператор '<' является иррефлексивным.
10. , т. е. порядок удовлетворяет трихотомии.
11. , то есть порядок сохраняется при добавлении того же элемента.
12. , т.е. порядок сохраняется при умножении на один и тот же положительный элемент.
13. , т.е. для любых двух различных элементов больший является меньшим плюс еще один элемент.
14. , т.е. ноль и единица различны и есть между ними нет элемента.
15. $\forall \; x\; (x\; \ge \; 0)\; \{\backslash \; displaystyle\; \backslash \; forall\; x\; \backslash \; (x\; \backslash \; geq\; 0)\}$, т.е. ноль - это минимальный элемент.

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

Модели

A модель аксиом Пеано представляет собой тройку (N, 0, S), где N - (обязательно бесконечное) множество, 0 ∈ N и S: N→ Nудовлетворяет аксиомам выше. Дедекинд доказал в своей книге 1888 года «Природа и значение чисел» (немецкий : Was sind und was sollen die Zahlen ?, т. Е. «Что такое числа и для чего они нужны? ? ”), Что любые две модели аксиом Пеано (включая аксиому индукции второго порядка) изоморфны. В частности, учитывая две модели (NA, 0 A, S A) и (NB, 0 B, S B) аксиом Пеано существует единственный гомоморфизм f: NA→ NB, удовлетворяющий

$f\; (0\; A)\; =\; 0\; B\; f\; (SA\; (n))\; =\; SB\; (f\; (n))\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; f\; (0\_\; \{A\})\; =\; 0\_\; \{B\}\; \backslash \backslash \; f\; (S\_\; \{A\}\; (n))\; =\; S\_\; \{B\}\; (f\; (n))\; \backslash \; end\; \{\; выровнено\}\}\}$

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

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

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

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

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

$0\; =\; \varnothing \; 1\; =\; s\; (0)\; =\; s\; (\varnothing )\; =\; \varnothing \; \cup \; \{\varnothing \}\; =\; \{\varnothing \}\; =\; \{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\}\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; 0\; =\; \backslash \; emptyset\; \backslash \backslash \; 1\; =\; s\; (0)\; =\; s\; (\backslash \; emptyset)\; =\; \backslash \; emptyset\; \backslash \; cup\; \backslash \; \{\backslash \; emptyset\; \backslash \}\; =\; \backslash \; \{\backslash \; emptyset\; \backslash \}\; =\; \backslash \; \{0\; \backslash \}\; \backslash \backslash \; 2\; =\; s\; (1)\; =\; s\; (\backslash \; \{0\; \backslash \})\; =\; \backslash \; \{0\; \backslash \}\; \backslash \; чашка\; \backslash \; \{\backslash \; \{0\; \backslash \}\; \backslash \}\; =\; \backslash \; \{0,\; \backslash \; \{0\; \backslash \}\; \backslash \}\; =\; \backslash \; \{0,1\; \backslash \}\; \backslash \backslash \; 3\; =\; s\; (2)\; =\; s\; (\backslash \; \{0,1\; \backslash \})\; =\; \backslash \; \{0,1\; \backslash \}\; \backslash \; cup\; \backslash \; \{\backslash \; \{0,1\; \backslash \}\; \backslash \}\; =\; \backslash \; \{0,1,\; \backslash \; \{0,1\; \backslash \}\; \backslash \}\; =\; \backslash \; \{0,1,2\; \backslash \}\; \backslash \; end\; \{align\}\}\}$

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

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

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

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

• Объекты US 1 (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) таково, что

$u\; 0\; =\; 0\; X,\; u\; (S\; x)\; =\; SX\; (ux).\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; u0\; =\; 0\_\; \{X\},\; \backslash \backslash \; u\; (Sx)\; =\; S\_\; \{X\}\; (ux).\; \backslash \; end\; \{align\}\}\}$

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

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

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

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

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

Overspill

A cut в нестандартной модели M - это непустое подмножество C в M, так что C замкнуто вниз (x

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

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

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

$M\; \models \; \varphi \; (c,\; a\; ¯).\; \{\backslash \; displaystyle\; M\; \backslash \; vDash\; \backslash \; phi\; (c,\; \{\backslash \; bar\; \{a\}\}).\}$

Согласованность

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

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

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

См. также

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

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

Примечания

Ссылки

Цитаты

Источники

Дополнительная литература

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

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

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

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