Формальная арифметика Пеано

Формальная арифметика Пеано (также аксиоматика Пеано, PA) — это формальная система первого порядка, аксиоматизирующая натуральные числа с операциями сложения и умножения. Предложена итальянским математиком Джузеппе Пеано в 1889 году. Является одной из фундаментальных теорий в основаниях математики, логике и теории вычислимости. Система PA служит стандартным примером непротиворечивой, но неполной теории (в смысле теорем Гёделя о неполноте).

История

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

До работ Пеано попытки строгого определения натуральных чисел предпринимались в рамках арифметики и логики. Рихард Дедекинд в 1888 году в работе «Что такое числа и для чего они служат?» предложил аксиоматику, основанную на понятии «цепочки» (Kette) и отображения следования. Дедекинд ввёл аксиомы, эквивалентные аксиомам Пеано, но его работа была менее известна. Пеано, ознакомившись с трудом Дедекинда, создал более компактную и логически ясную систему.

Работа Пеано (1889)

В 1889 году Пеано опубликовал книгу «Arithmetices principia, nova methodo exposita» («Принципы арифметики, изложенные новым методом»). В ней он впервые сформулировал девять аксиом (пять для натуральных чисел и четыре для равенства), используя символический язык логики, разработанный Готлобом Фреге и Бертраном Расселом. Пеано ввёл обозначения: 0 (или 1 в некоторых версиях), функция следования S, а также аксиомы индукции. Его работа заложила основу для формальной арифметики как раздела математической логики.

Развитие в XX веке

В начале XX века аксиоматика Пеано была уточнена и формализована в рамках логики первого порядка. Курт Гёдель в 1931 году доказал теоремы о неполноте, показав, что в любой непротиворечивой формальной системе, включающей арифметику Пеано, существуют истинные, но недоказуемые утверждения. Это открытие имело огромное значение для оснований математики. В дальнейшем PA изучалась в теории моделей (модели нестандартной арифметики) и теории вычислимости (связь с рекурсивными функциями).

Аксиомы

Формальная арифметика Пеано (PA) строится на языке первого порядка, содержащем:

• Константу 0 (ноль).
• Одноместный функциональный символ S (функция следования, «следующее за»).
• Двуместные функциональные символы + (сложение) и · (умножение).

Аксиомы PA делятся на две группы: логические аксиомы и собственно аксиомы Пеано.

Аксиомы равенства

1. ∀x (x = x) — рефлексивность.
2. ∀x∀y (x = y → y = x) — симметричность.
3. ∀x∀y∀z (x = y ∧ y = z → x = z) — транзитивность.
4. Для каждого функционального символа f (S, +, ·) и каждого предиката =: аксиомы подстановочности (конгруэнтности). Например: ∀x∀y (x = y → S(x) = S(y)).

Аксиомы Пеано (нелогические)

1. ∀x (S(x) ≠ 0) — ноль не является следующим ни за каким числом.
2. ∀x∀y (S(x) = S(y) → x = y) — функция следования инъективна (разные числа имеют разных последователей).
3. ∀x (x + 0 = x) — определение сложения с нулём.
4. ∀x∀y (x + S(y) = S(x + y)) — рекурсивное определение сложения.
5. ∀x (x · 0 = 0) — определение умножения на ноль.
6. ∀x∀y (x · S(y) = (x · y) + x) — рекурсивное определение умножения.

Схема аксиом индукции

Для любой формулы φ(x) с одной свободной переменной x (возможно, с параметрами) аксиома: (φ(0) ∧ ∀x (φ(x) → φ(S(x)))) → ∀x φ(x)

Эта схема бесконечна (счётное число аксиом) и является ключевой для PA, так как позволяет доказывать свойства всех натуральных чисел.

Свойства

Непротиворечивость

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

Полнота и неполнота

PA не является полной теорией. Первая теорема Гёделя о неполноте утверждает, что в любой непротиворечивой рекурсивно аксиоматизируемой теории, содержащей арифметику, существует истинное, но недоказуемое утверждение (так называемое «гёделево предложение»). Для PA таким примером является утверждение о непротиворечивости самой PA (Con(PA)). Существуют и другие недоказуемые утверждения, например, теорема Гудстейна или проблема Варинга для некоторых чисел.

Разрешимость

Теория PA неразрешима: не существует алгоритма, который для произвольного утверждения на языке PA мог бы определить, истинно оно в стандартной модели или нет. Это следует из теоремы Чёрча о неразрешимости логики первого порядка и из того, что PA достаточно выразительна для кодирования рекурсивных функций.

Категоричность

PA не является категоричной теорией: у неё есть нестандартные модели. Помимо стандартной модели (множество натуральных чисел ℕ с обычными операциями), существуют модели, содержащие «бесконечные» числа (элементы, большие всех стандартных натуральных чисел). Эти модели удовлетворяют всем аксиомам PA, но имеют порядковый тип ω + (ω* + ω) · η, где η — порядковый тип рациональных чисел.

Модели

Стандартная модель

Стандартная модель PA — это множество натуральных чисел ℕ = {0, 1, 2, …} с обычными операциями сложения и умножения. В этой модели все аксиомы PA истинны. Стандартная модель является минимальной в том смысле, что любая другая модель содержит изоморфную копию ℕ.

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

Нестандартные модели PA содержат, помимо стандартных чисел, «нестандартные» элементы (бесконечные числа). В таких моделях аксиома индукции выполняется только для формул, определённых в языке, но не для всех подмножеств (так как в PA нет аксиомы выбора для произвольных множеств). Нестандартные модели изучаются в теории моделей и имеют порядковый тип ω + (ω* + ω) · η. Примером является модель, построенная с помощью теоремы компактности: добавление константы c и аксиом c > 0, c > S(0), c > S(S(0)), … даёт непротиворечивую теорию, модель которой нестандартна.

Применение

В основаниях математики

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

В теории вычислимости

PA тесно связана с рекурсивными функциями: класс функций, вычислимых на машине Тьюринга, совпадает с классом функций, определимых в PA. Это позволяет использовать PA для доказательства неразрешимости алгоритмических проблем.

В логике и философии

Теоремы Гёделя о неполноте, доказанные для PA, имеют глубокие философские следствия о пределах формальных систем. Они показывают, что никакая непротиворечивая аксиоматическая система, достаточная для арифметики, не может быть одновременно полной и непротиворечивой.

Критика и ограничения

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

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

Выразительная сила

PA не может выразить некоторые понятия, например, «конечность» или «счётность» в общем виде. Для работы с бесконечными множествами требуется теория множеств. Кроме того, PA не позволяет доказывать утверждения, требующие индукции по формулам, не представимым в языке первого порядка.

Сложность доказательств

Некоторые простые с человеческой точки зрения утверждения (например, теорема о четырёх красках) могут требовать очень длинных доказательств в PA, если они вообще доказуемы. Это связано с ограниченностью схемы индукции.

Связь с другими теориями

Арифметика Робинсона (Q)

Арифметика Робинсона (Q) — это ослабленная версия PA, в которой отсутствует схема аксиом индукции. Q является конечно аксиоматизируемой и также неполной, но её выразительная сила меньше. Q используется для доказательства теорем о неполноте в более слабых системах.

Арифметика второго порядка (PA₂)

Арифметика второго порядка (PA₂) — это расширение PA, в котором разрешены кванторы по множествам натуральных чисел. PA₂ является категоричной (все её модели изоморфны стандартной модели ℕ) и позволяет доказывать многие теоремы, недоказуемые в PA. Однако PA₂ не является формальной системой первого порядка и имеет более сложную логику.

Теория множеств ZFC

Теория множеств Цермело — Френкеля с аксиомой выбора (ZFC) является более сильной теорией, в которой можно интерпретировать PA. В ZFC доказывается непротиворечивость PA, но сама ZFC также подчиняется теоремам Гёделя о неполноте.

Интересные факты

• Первоначально Пеано использовал 1 в качестве начального числа, но в современной версии чаще используется 0.
• Аксиоматика Пеано является одной из первых успешных попыток аксиоматизации математической теории.
• Теорема Гудстейна (1944) является примером истинного арифметического утверждения, которое недоказуемо в PA, но доказуемо в более сильной теории (арифметике второго порядка).
• Нестандартные модели PA были впервые построены в 1930-х годах с помощью теоремы компактности и теории ультрафильтров.

Источники

• Пеано, Джузеппе. Arithmetices principia, nova methodo exposita. — 1889.
• Гёдель, Курт. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. — 1931.
• Мендельсон, Эллиотт. Введение в математическую логику. — 5-е изд. — Chapman and Hall, 2009. — Глава 3.
• Кейслер, Г. Дж., Чен, Ч. Ч. Теория моделей. — Elsevier, 1990. — Глава 5.
• Тарский, Альфред. Неразрешимые теории. — North-Holland, 1953.