В математической логике аксиомы Пеано ( / p i ˈ ɑː n oʊ / , [1] [peˈaːno] ), также известные как аксиомы Дедекинда-Пеано или постулаты Пеано , являются аксиомами натуральных чисел , представленными 19-м веком. Итальянский математик Джузеппе Пеано . Эти аксиомы использовались почти без изменений в ряде метаматематических исследований, включая исследования фундаментальных вопросов о том, является ли теория чисел последовательной и полной .
Важность формализации арифметики не была оценена должным образом до работы Германа Грассмана , который в 1860-х годах показал, что многие факты в арифметике могут быть выведены из более фундаментальных фактов о последующих операциях и индукции . [2] [3] В 1881 году Чарльз Сандерс Пирс представил аксиоматизацию арифметики натуральных чисел. [4] [5] В 1888 году Ричард Дедекинд предложил еще одну аксиоматизацию арифметики натуральных чисел, а в 1889 году Пеано опубликовал упрощенную версию их в виде сборника аксиом в своей книге « Принципы арифметики, представленные новым методом» ( лат. : Принципы арифметики, новый метод экспозита ).
Девять аксиом Пеано содержат три типа утверждений. Первая аксиома утверждает существование хотя бы одного члена множества натуральных чисел. Следующие четыре являются общими утверждениями о равенстве ; в современных трактовках они часто рассматриваются не как часть аксиом Пеано, а скорее как аксиомы «основной логики». [6] Следующие три аксиомы представляют собой утверждения первого порядка о натуральных числах, выражающие фундаментальные свойства последующей операции. Девятая, последняя аксиома — это утверждение второго порядка принципа математической индукции по натуральным числам, что делает эту формулировку близкой к арифметике второго порядка . Более слабая система первого порядка, называемая арифметикой Пеано , получается путем явного добавления символов операций сложения и умножения и замены аксиомы индукции второго порядка схемой аксиом первого порядка .
Когда Пеано сформулировал свои аксиомы, язык математической логики находился в зачаточном состоянии. Система логических обозначений, которую он создал для представления аксиом, не оказалась популярной, хотя она и послужила источником современной записи членства во множестве (ε, которая происходит от ε Пеано). Пеано проводил четкое различие между математическими и логическими символами, что еще не было распространено в математике; такое разделение было впервые введено в Begriffsschrift Готлоба Фреге , опубликованном в 1879 году. [7] Пеано не знал о работах Фреге и самостоятельно воссоздал свой логический аппарат на основе работ Буля и Шредера . [8]
Аксиомы Пеано определяют арифметические свойства натуральных чисел , обычно представленных в виде набора N или Нелогические символы аксиом состоят из постоянного символа 0 и символа унарной функции S.
Первая аксиома гласит, что константа 0 является натуральным числом:
В первоначальной формулировке аксиом Пеано в качестве «первого» натурального числа использовалась 1 вместо 0, [9] тогда как аксиомы в Formulario Mathematico включают ноль. [10]
Следующие четыре аксиомы описывают отношение равенства . Поскольку они логически действительны в логике первого порядка с равенством, они не считаются частью «аксиом Пеано» в современных трактовках. [8]
Остальные аксиомы определяют арифметические свойства натуральных чисел. Предполагается , что натуральные числа замкнуты относительно однозначной функции « преемника » S.
Аксиомы 1, 6, 7, 8 определяют одноместное представление интуитивного понятия натуральных чисел: число 1 можно определить как S (0), 2 как S ( S (0)) и т.д. Однако, учитывая понятие натуральные числа, определенные этими аксиомами, аксиомы 1, 6, 7, 8 не означают, что функция-преемник генерирует все натуральные числа, отличные от 0.
Интуитивное представление о том, что каждое натуральное число можно получить, применяя преемник достаточно много раз к нулю, требует дополнительной аксиомы, которую иногда называют аксиомой индукции .
Аксиому индукции иногда формулируют в следующем виде:
В исходной формулировке Пеано аксиома индукции является аксиомой второго порядка . Сейчас принято заменять этот принцип второго порядка более слабой схемой индукции первого порядка . Между формулировками второго и первого порядка существуют важные различия, как обсуждается в разделе § Арифметика Пеано как теория первого порядка ниже.
Если мы используем аксиому индукции второго порядка, можно определить сложение , умножение и полный (линейный) порядок на N непосредственно с помощью аксиом. Однако при индукции первого порядка это невозможно, и сложение и умножение часто добавляются в качестве аксиом. Соответствующие функции и отношения строятся в теории множеств или логике второго порядка , и их уникальность можно показать с помощью аксиом Пеано.
Сложение — это функция, которая отображает два натуральных числа (два элемента N ) в другое. Он определяется рекурсивно как:
Например:
Структура ( N , + ) представляет собой коммутативный моноид с единичным элементом 0. ( N , + ) также является сокращающейся магмой и, следовательно , вкладывается в группу . Наименьшая группа, включающая N , — это целые числа .
Аналогично, умножение — это функция, переводящая два натуральных числа в другое. Учитывая сложение, он определяется рекурсивно как:
Легко видеть, что это мультипликативное правое тождество :
Чтобы показать, что это также мультипликативная левая идентичность, требуется аксиома индукции из-за способа определения умножения:
Следовательно, по аксиоме индукции есть мультипликативная левая единица всех натуральных чисел. Более того, можно показать, что умножение коммутативно и распределяется по сложению:
Таким образом, – коммутативное полукольцо .
Обычное отношение полного порядка ≤ для натуральных чисел можно определить следующим образом, предполагая, что 0 — натуральное число:
Это отношение устойчиво относительно сложения и умножения: при , если a ≤ b , то:
Таким образом, структура ( N , +, ·, 1, 0, ≤) является упорядоченным полукольцом ; поскольку между 0 и 1 нет натурального числа, это дискретное упорядоченное полукольцо.
Аксиому индукции иногда формулируют в следующей форме, в которой используется более сильная гипотеза с использованием отношения порядка «≤»:
Эта форма аксиомы индукции, называемая сильной индукцией , является следствием стандартной формулировки, но часто лучше подходит для рассуждений о порядке ≤. Например, чтобы показать, что натуральные числа хорошо упорядочены — каждое непустое подмножество N имеет наименьший элемент — можно рассуждать следующим образом. Пусть задан непустой X ⊆ N и предположим , что 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 , удовлетворяющий условиям
и это биекция . Это означает, что аксиомы Пеано второго порядка категоричны . (Это не относится к любой переформулировке аксиом Пеано первого порядка, приведенной ниже.)
Аксиомы Пеано могут быть получены из теоретико-множественных конструкций натуральных чисел и аксиом теории множеств, таких как ZF . [14] Стандартная конструкция натуральных чисел, предложенная Джоном фон Нейманом , начинается с определения 0 как пустого множества ∅ и оператора s на множествах, определяемых как:
Множество натуральных чисел N определяется как пересечение всех замкнутых относительно s множеств , содержащих пустое множество. Каждое натуральное число равно (как множество) множеству натуральных чисел, меньших его:
и так далее. Множество N вместе с 0 и функцией-преемником s : N → N удовлетворяет аксиомам Пеано.
Арифметика Пеано равносовместима с несколькими слабыми системами теории множеств. [15] Одной из таких систем является ZFC, в которой аксиома бесконечности заменена ее отрицанием. Другая такая система состоит из общей теории множеств ( экстенсиональность , существование пустого множества и аксиома присоединения ), дополненной схемой аксиом, утверждающей, что свойство, которое справедливо для пустого множества и справедливо для присоединения всякий раз, когда оно справедливо для присоединения. должно соблюдаться для всех наборов.
Аксиомы Пеано также можно понять с помощью теории категорий . Пусть C — категория с терминальным объектом 1 C и определите категорию точечных унарных систем US 1 ( C ) следующим образом:
Тогда говорят, что C удовлетворяет аксиомам Дедекинда – Пеано, если US 1 ( C ) имеет начальный объект; этот исходный объект известен как объект натурального числа в C. Если ( N , 0, S ) — этот исходный объект, а ( X , 0 X , S X ) — любой другой объект, то уникальное отображение u : ( N , 0, S ) → ( X , 0 X , S X ) таков, что
Это и есть рекурсивное определение 0 X и S X .
Когда аксиомы Пеано были впервые предложены, Бертран Рассел и другие согласились, что эти аксиомы неявно определяют, что мы подразумеваем под «натуральным числом». [16] Анри Пуанкаре был более осторожен, говоря, что они определяют натуральные числа только в том случае, если они непротиворечивы ; если существует доказательство, которое начинается только с этих аксиом и приводит к противоречию, такому как 0 = 1, то аксиомы противоречивы и ничего не определяют. [17] В 1900 году Дэвид Гильберт поставил задачу доказательства их непротиворечивости с использованием только финитистских методов в качестве второй из своих двадцати трёх задач . [18] В 1931 году Курт Гёдель доказал свою вторую теорему о неполноте , которая показывает, что такое доказательство непротиворечивости не может быть формализовано внутри самой арифметики Пеано, если арифметика Пеано непротиворечива. [19]
Хотя широко утверждается, что теорема Гёделя исключает возможность финитистского доказательства непротиворечивости арифметики Пеано, это зависит от того, что именно понимать под финитистским доказательством. Сам Гёдель указывал на возможность дать финитистское доказательство непротиворечивости арифметики Пеано или более сильных систем с помощью финитистских методов, которые не формализуемы в арифметике Пеано, и в 1958 году Гёдель опубликовал метод доказательства непротиворечивости арифметики с использованием теории типов . [20] В 1936 году Герхард Генцен дал доказательство непротиворечивости аксиом Пеано, используя трансфинитную индукцию до порядкового номера , называемого ε 0 . [21] Генцен объяснил: «Цель настоящей статьи — доказать непротиворечивость элементарной теории чисел или, скорее, свести вопрос непротиворечивости к некоторым фундаментальным принципам». Доказательство Генцена, возможно, является финитистским, поскольку трансфинитный ординал ε 0 может быть закодирован в терминах конечных объектов (например, как машина Тьюринга , описывающая подходящий порядок целых чисел, или, более абстрактно, как состоящая из конечных деревьев , соответствующим образом линейно упорядоченных) . Неясно, отвечает ли доказательство Генцена требованиям, предусмотренным Гильбертом: не существует общепринятого определения того, что именно подразумевается под финитистским доказательством, а сам Гильберт никогда не давал точного определения.
Подавляющее большинство современных математиков считают, что аксиомы Пеано непротиворечивы, полагаясь либо на интуицию, либо на принятие доказательства непротиворечивости, такого как доказательство Генцена . Небольшое количество философов и математиков, некоторые из которых также выступают за ультрафинитизм , отвергают аксиомы Пеано, потому что принятие аксиом равносильно признанию бесконечного набора натуральных чисел. В частности, предполагается, что сложение (включая функцию-преемник) и умножение являются полными . Любопытно, что существуют самопроверяющиеся теории , подобные ПА, но имеющие вычитание и деление вместо сложения и умножения, которые аксиоматизируются таким образом, чтобы избежать доказательства предложений, соответствующих совокупности сложения и умножения, но которые все же способны чтобы доказать все истинные теоремы PA, и, тем не менее, может быть расширено до непротиворечивой теории, которая доказывает свою собственную непротиворечивость (заявленную как отсутствие доказательства в стиле Гильберта «0 = 1»). [22]
Все аксиомы Пеано, за исключением девятой аксиомы (аксиомы индукции), являются утверждениями логики первого порядка . [23] Арифметические операции сложения и умножения, а также отношение порядка также могут быть определены с использованием аксиом первого порядка. Приведенная выше аксиома индукции имеет второй порядок , поскольку она дает количественную оценку предикатам (т. е. множествам натуральных чисел, а не натуральных чисел). В качестве альтернативы можно рассмотреть схему аксиом индукции первого порядка. Такая схема включает в себя одну аксиому на каждый предикат, определяемый на языке арифметики Пеано первого порядка, что делает ее более слабой, чем аксиома второго порядка. [24] Причина, по которой он слабее, заключается в том, что количество предикатов в языке первого порядка счетно, тогда как количество наборов натуральных чисел несчетно. Таким образом, существуют множества, которые невозможно описать на языке первого порядка (фактически большинство множеств обладают этим свойством).
Аксиоматизации первого порядка арифметики Пеано имеют еще одно техническое ограничение. В логике второго порядка можно определить операции сложения и умножения из операции-преемника , но это невозможно сделать в более ограничительной настройке логики первого порядка. Поэтому операции сложения и умножения непосредственно включены в сигнатуру арифметики Пеано, а также включены аксиомы, связывающие эти три операции друг с другом.
Для этой цели достаточен следующий список аксиом (наряду с обычными аксиомами равенства), содержащий шесть из семи аксиом арифметики Робинсона : [25]
Помимо этого списка числовых аксиом, арифметика Пеано содержит схему индукции, состоящую из рекурсивно перечислимого и даже разрешимого набора аксиом . Для каждой формулы φ ( x , y 1 , ..., y k ) на языке арифметики Пеано аксиомой индукции первого порядка для φ является предложение
где – сокращение для y 1 ,..., y k . Схема индукции первого порядка включает в себя каждый экземпляр аксиомы индукции первого порядка; то есть он включает аксиому индукции для каждой формулы φ .
Приведенная выше аксиоматизация арифметики Пеано использует сигнатуру, которая имеет только символы нуля, а также операции-преемники, сложения и умножения. Есть много других различных, но эквивалентных аксиоматизаций. Одна из таких альтернатив [26] использует символ отношения порядка вместо операции-преемника и язык дискретно упорядоченных полуколец (аксиомы 1–7 для полуколец, 8–10 по порядку, 11–13 по совместимости и 14–15 по дискретности). :
Теория, определяемая этими аксиомами, известна как PA − . Она также неполна, и одно из ее важных свойств состоит в том, что любая структура, удовлетворяющая этой теории, имеет начальный сегмент (упорядоченный ), изоморфный . Элементы в этом сегменте называются стандартными элементами, а другие элементы называются нестандартными элементами.
Наконец, арифметика Пеано PA получается добавлением схемы индукции первого порядка.
Согласно теоремам Гёделя о неполноте , теория ПА (если она непротиворечива) является неполной. Следовательно, существуют предложения логики первого порядка (ЛОЛ), которые истинны в стандартной модели ПА , но не являются следствием аксиоматизации ЛП. Существенная неполнота возникает уже для теорий с более слабыми аксиомами, таких как арифметика Робинсона .
Из этого, тесно связанного с приведенным выше результатом о неполноте (через теорему Гёделя о полноте для FOL), следует, что не существует алгоритма для определения того, является ли данное предложение FOL следствием аксиоматизации первого порядка арифметики Пеано или нет. Следовательно, PA является примером неразрешимой теории . Неразрешимость возникает уже для экзистенциальных предложений PA из-за отрицательного ответа на десятую проблему Гильберта , доказательство которой подразумевает, что все вычислимо перечислимые множества являются диофантовыми множествами и, следовательно, могут быть определены с помощью экзистенциально квантифицированных формул (со свободными переменными) PA . Формулы ПА с более высоким кванторным рангом (большее количество чередований кванторов), чем формулы существования, более выразительны и определяют множества на более высоких уровнях арифметической иерархии .
Хотя обычные натуральные числа удовлетворяют аксиомам PA, существуют и другие модели (называемые « нестандартными моделями »); из теоремы компактности следует , что существование нестандартных элементов не может быть исключено в логике первого порядка. [27] Восходящая теорема Левенхайма–Скулема показывает, что существуют нестандартные модели PA всех бесконечных мощностей. Это не относится к исходным аксиомам Пеано (второго порядка), которые имеют только одну модель с точностью до изоморфизма. [28] Это иллюстрирует один из способов, почему система PA первого порядка слабее, чем аксиомы Пеано второго порядка.
При интерпретации как доказательство в рамках теории множеств первого порядка , такой как ZFC , доказательство категоричности Дедекинда для PA показывает, что каждая модель теории множеств имеет уникальную модель аксиом Пеано, с точностью до изоморфизма, которая вкладывается как начальный сегмент всех другие модели ПА, содержащиеся в этой модели теории множеств. В стандартной модели теории множеств эта наименьшая модель ПА является стандартной моделью ПА; однако в нестандартной модели теории множеств это может быть нестандартная модель ПА. Этой ситуации невозможно избежать при любой формализации теории множеств первого порядка.
Естественно задаться вопросом, можно ли явно построить счетную нестандартную модель. Ответ утвердительный, поскольку Сколем в 1933 году предоставил явную конструкцию такой нестандартной модели . С другой стороны, теорема Тенненбаума , доказанная в 1959 году, показывает, что не существует счетной нестандартной модели ПА, в которой вычислима операция сложения или умножения . [29] Этот результат показывает, что трудно быть полностью явным при описании операций сложения и умножения счетной нестандартной модели PA. Существует только один возможный тип заказа счетной нестандартной модели. Полагая , что ω — тип порядка натуральных чисел, ζ — тип порядка целых чисел, а η — тип порядка рациональных чисел, тип порядка любой счетной нестандартной модели PA равен ω + ζ · η , что может быть визуализируется как копия натуральных чисел, за которой следует плотный линейный порядок копий целых чисел.
Разрез в нестандартной модели M — это непустое подмножество C в M , так что C замкнуто вниз ( x < y и y ∈ C ⇒ x ∈ C ), а C замкнуто относительно преемника. Правильный разрез — это разрез , который является правильным подмножеством M. Каждая нестандартная модель имеет множество правильных разрезов, в том числе тот, который соответствует стандартным натуральным числам. Однако схема индукции в арифметике Пеано не позволяет определить какой-либо правильный разрез. Лемма о переливе, впервые доказанная Абрахамом Робинсоном, формализует этот факт.
Лемма о перерасходе [30] — Пусть M — нестандартная модель PA, и пусть C — собственный разрез M . Предположим, что это кортеж элементов M и формула на языке арифметики так, что
Тогда в M существует элемент c , больший любого элемента C, такой, что
{{cite book}}
: CS1 maint: multiple names: authors list (link){{cite book}}
: CS1 maint: location missing publisher (link)Эта статья включает в себя материалы от PA на PlanetMath , которые доступны под лицензией Creative Commons Attribution/Share-Alike License .