Арифметика Пеано

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

История

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

Первоначальная версия Пеано была изложена в терминах теории множеств и логики первого порядка, однако в дальнейшем (в работах второй половины XX века) для арифметики Пеано была принята стандартная формальная запись в логике первого порядка с языком, содержащим константу «0» (ноль), одноместную функцию «s» (функция следования) и двухместные функции «+» и «·». Эта версия получила название PA (Peano Arithmetic).

Аксиомы

Аксиомы Пеано описывают натуральный ряд, начиная с нуля. В классической формулировке они включают пять утверждений:

1. Ноль — натуральное число: 0 ∈ ℕ.
2. Замкнутость относительно следования: Если n — натуральное число, то s(n) (следующее за n) — тоже натуральное число.
3. Инъективность следования: Если s(n) = s(m), то n = m (разные числа имеют разные следующие).
4. Нуль не является следующим ни для какого числа: Не существует такого n, что s(n) = 0.
5. Аксиома индукции: Если некоторое свойство P(n) истинно для 0 и из истинности P(n) следует истинность P(s(n)) для любого натурального n, то P(n) истинно для всех натуральных чисел.

Аксиома индукции и её формализация

В исходной формулировке Пеано аксиома индукции была сформулирована как свойство второго порядка (то есть как утверждение о всех подмножествах натуральных чисел). В современной «слабой» (или «элементарной») арифметике Пеано (PA) аксиома индукции заменяется схемой аксиом: для каждой формулы φ(x) логики первого порядка, записываемой на языке арифметики, добавляется отдельная аксиома: (φ(0) ∧ ∀x (φ(x) → φ(s(x)))) → ∀x φ(x). Таким образом, PA — это теория первого порядка с бесконечным числом аксиом (по одной на каждую формулу). Этот вариант аксиоматизации, хотя и слабее исходной версии второго порядка, является наиболее часто изучаемым в математической логике.

Свойства арифметики Пеано

Непротиворечивость и неполнота

В 1931 году Курт Гёдель доказал две знаменитые теоремы о неполноте, которые имеют прямое отношение к арифметике Пеано:

• Первая теорема Гёделя: Если PA непротиворечива, то она неполна — существуют истинные (в стандартной модели натуральных чисел) утверждения, которые не могут быть ни доказаны, ни опровергнуты в рамках PA.
• Вторая теорема Гёделя: Непротиворечивость PA не может быть доказана средствами самой PA (если она непротиворечива). Для доказательства непротиворечивости PA требуется более сильная теория (например, арифметика второго порядка или теория множеств ZFC).

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

Стандартная модель PA — это множество натуральных чисел ℕ = {0, 1, 2, …) с обычными операциями сложения и умножения.

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

Выразимость и алгоритмическая неразрешимость

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

Применение и значение

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

В информатике арифметика Пеано используется для:

• Проверки и верификации программ: Многие системы формальной верификации (например, Coq, Isabelle) реализуют аксиоматику натуральных чисел, близкую к PA.
• Теории вычислимости: Понятие рекурсивных функций, тесно связанных с аксиомами PA, лежит в основе определения алгоритмических процессов.

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

Теорема Гёделя и границы PA

Фактически, из-за теоремы Гёделя, арифметика Пеано не может сама себя «доказать» как непротиворечивую. Это привело к разработке так называемой «арифметики второго порядка» (PA2), где аксиома индукции формулируется как одно утверждение о всех подмножествах, а не как схема для каждого предиката. Арифметика второго порядка значительно сильнее, но также подпадает под действие первой теоремы Гёделя (она неполна), хотя её непротиворечивость может быть установлена в рамках теории множеств.

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

• Арифметика с навешиванием кванторов (PA) vs. арифметика с индукцией без кванторов (I∆₀): Существуют фрагменты PA, где аксиома индукции применяется только к формулам определённой сложности (например, только к ограниченным формулам). Такие теории, как I∆₀, слабее, но всё ещё способны доказывать многие классические результаты.
• Арифметика Робинсона (Q): Более слабая система, чем PA, не содержащая аксиомы индукции. Она фрагментарна, но достаточно выразительна для формулировки теорем Гёделя.
• Теория множеств ZFC: В ZFC классическая арифметика Пеано (в стандартной модели) может быть построена как теория натуральных чисел, определённых через ординалы фон Неймана.

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

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

Несмотря на эти ограничения, арифметика Пеано остаётся ключевым инструментом для понимания границ формализации и природы математического доказательства.

Источники

• Пеано, Д. (1889). Arithmetices principia, nova methodo exposita.
• Гёдель, К. (1931). «О формально неразрешимых предложениях Principia Mathematica и родственных систем», Monatshefte für Mathematik und Physik, 38, 173–198.
• Мендельсон, Э. (2009). Введение в математическую логику. М.: Наука.
• Скворцов, Д. П. (1987). Математическая логика. М.: Высшая школа.
• Френкель, А. А. (1966). Основания теории множеств. М.: Мир.