Аксиомы Пеано - Peano axioms

В математическая логика, то Аксиомы Пеано, также известный как Аксиомы Дедекинда – Пеано или Постулаты Пеано, находятся аксиомы для натуральные числа представлены 19 веком Итальянский математик Джузеппе Пеано. Эти аксиомы использовались практически без изменений в ряде метаматематический расследования, в том числе исследования фундаментальных вопросов: теория чисел является последовательный и полный.

Необходимость формализации арифметика не был хорошо оценен, пока работа Герман Грассманн, который показал в 1860-х годах, что многие арифметические факты можно вывести из более основных фактов о последующая операция и индукция.[1] В 1881 г. Чарльз Сандерс Пирс предоставил аксиоматизация арифметики натуральных чисел.[2] В 1888 г. Ричард Дедекинд предложил другую аксиоматизацию арифметики натуральных чисел, и в 1889 году Пеано опубликовал их упрощенную версию в виде сборника аксиом в своей книге: Принципы арифметики представлены по новой методике (латинский: Принципы арифметики, новая методика экспозиции).

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

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

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

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

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

  1. 0 - натуральное число.

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

  1. Для каждого натурального числа Икс, Икс = Икс. То есть равенство рефлексивный.
  2. Для всех натуральных чисел Икс и у, если Икс = у, тогда у = Икс. То есть равенство симметричный.
  3. Для всех натуральных чисел Икс, у и z, если Икс = у и у = z, тогда Икс = z. То есть равенство переходный.
  4. Для всех а и б, если б натуральное число и а = б, тогда а тоже натуральное число. То есть натуральные числа закрыто при равенстве.

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

  1. Для каждого натурального числа п, S(п) - натуральное число. То есть натуральные числа закрыто под S.
  2. Для всех натуральных чисел м и п, м = п если и только если S(м) = S(п). То есть, S является инъекция.
  3. Для каждого натурального числа п, S(п) = 0 ложно. То есть не существует натурального числа, последователем которого является 0.

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

Аксиомы 1, 6, 7, 8 определяют унарное представление интуитивного понятия натуральных чисел: число 1 можно определить как S(0), 2 как S(S(0)) и т. Д. Однако, учитывая, что понятие натуральных чисел определяется этими аксиомами, аксиомы 1, 6, 7, 8 не означают, что функция-последователь генерирует все натуральные числа, отличные от 0. Иными словами, они не гарантируют, что каждое натуральное число, кроме нуля, должно следовать за каким-либо другим натуральным числом.

Интуитивное представление о том, что каждое натуральное число можно получить, применяя преемник достаточно часто к нулю требует дополнительной аксиомы, которую иногда называют аксиома индукции.

  1. Если K такой набор, что:
    • 0 находится в K, и
    • для каждого натурального числа п, п находясь в K подразумевает, что S(п) в K,
    тогда K содержит каждое натуральное число.

Аксиому индукции иногда формулируют в следующем виде:

  1. Если φ унарный предикат такой, что:
    • φ(0) верно, и
    • для каждого натурального числа п, φ(п) истинность означает, что φ(S(п)) правда,
    тогда φ(п) верно для любого натурального числа п.

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

Арифметика

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

Добавление

Добавление это функция, которая карты два натуральных числа (два элемента N) к другому. Это определено рекурсивно в качестве:

Например:

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

Умножение

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

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

Чтобы показать это также мультипликативное левое тождество требует аксиомы индукции из-за способа определения умножения:

  • левое тождество 0: .
  • Если левое тождество (то есть ), тогда также является левым тождеством : .

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

.

Таким образом, коммутативный полукольцо.

Неравенства

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

Для всех а, бN, аб тогда и только тогда, когда существует cN такой, что а + c = б.

Это отношение устойчиво относительно сложения и умножения: при , если аб, тогда:

  • а + cб + c, и
  • а · cб · c.

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

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

Для любого предикат φ, если
  • φ(0) верно, и
  • для каждого п, kN, если kп подразумевает, что φ(k) верно, то φ(S(п)) правда,
затем для каждого пN, φ(п) правда.

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

  • Поскольку 0 - наименьший элемент N, это должно быть так 0 ∉ Икс.
  • Для любого пN, предположим для каждого kп, kИкс. потом S(п) ∉ Икс, иначе это был бы наименьший элемент Икс.

Таким образом, по принципу сильной индукции для каждого пN, пИкс. Таким образом, ИксN = ∅, который противоречит Икс быть непустым подмножеством N. Таким образом Икс имеет наименьший элемент.

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

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

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

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

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

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

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

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

  1. , т.е. сложение ассоциативный.
  2. , т.е. сложение коммутативный.
  3. , т.е. умножение ассоциативно.
  4. , т.е. умножение коммутативно.
  5. , т.е. умножение распределяет сверх сложения.
  6. , т.е. ноль - это личность для дополнения и поглощающий элемент для умножения (собственно лишнее[примечание 1]).
  7. , т. е. один личность для умножения.
  8. , т.е. оператор '<' переходный.
  9. , т.е. оператор '<' иррефлексивный.
  10. , т. е. порядок удовлетворяет трихотомия.
  11. , т.е. порядок сохраняется при добавлении того же элемента.
  12. , т.е. порядок сохраняется при умножении на тот же положительный элемент.
  13. , т.е. для любых двух различных элементов, чем больше, тем меньше плюс еще один элемент.
  14. , т.е. ноль и единица различны, и между ними нет элемента.
  15. , т.е. ноль - это минимальный элемент.

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

Модели

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

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

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

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

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

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

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

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

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

  • Объекты США1(C) тройки (Икс, 0Икс, SИкс) куда Икс является объектом C, и 0Икс : 1CИкс и SИкс : ИксИкс находятся C-морфизмы.
  • Морфизм φ : (Икс, 0Икс, SИкс) → (Y, 0Y, SY) это C-морфизм φ : ИксY с φ 0Икс = 0Y и φ SИкс = SY φ.

потом C считается удовлетворяющим аксиомам Дедекинда – Пеано, если US1(C) имеет исходный объект; этот исходный объект известен как объект натурального числа в C. Если (N, 0, S) это исходный объект, и (Икс, 0Икс, SИкс) любой другой объект, то уникальная карта ты : (N, 0, S) → (Икс, 0Икс, SИкс) таково, что

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

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

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

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

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

Переполнение

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

Лемма о чрезмерном количестве[16] Позволять M - нестандартная модель ПА и пусть C быть правильным вырезом из M. Предположим, что набор элементов M и это формула на языке арифметики, так что
для всех бC.
Тогда есть c в M это больше, чем каждый элемент C такой, что

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

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

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

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

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

Примечания

  1. ^ ""можно доказать из других аксиом (в логике первого порядка) следующим образом. Во-первых, по распределенности и аддитивной идентичности. Во-вторых, Аксиомой 15. Если тогда добавлением того же элемента и коммутативности, и, следовательно, путем подмены, противоречащей иррефлексивности. Следовательно, должно быть, что .

Рекомендации

Цитаты

  1. ^ Грассман 1861.
  2. ^ Пирс 1881, Щиты 1997
  3. ^ van Heijenoort 1967, п. 94.
  4. ^ van Heijenoort 1967, п. 2.
  5. ^ а б van Heijenoort 1967, п. 83.
  6. ^ Пеано 1889, п. 1.
  7. ^ Partee, Ter Meulen & Wall 2012, п. 215.
  8. ^ Харшаньи (1983).
  9. ^ Мендельсон 1997, п. 155.
  10. ^ Кэй 1991 С. 16–18.
  11. ^ Суппес 1960, Хэтчер 2014
  12. ^ Тарски и Гивант 1987, Раздел 7.6.
  13. ^ Гермес 1973, VI.4.3, представляя теорему Торальф Сколем
  14. ^ Гермес 1973, VI.3.1.
  15. ^ Кэй 1991, Раздел 11.3.
  16. ^ Кэй 1991, стр. 70 и далее.
  17. ^ Фриц 1952, п. 137
    Иллюстрацией «интерпретации» является собственное определение Расселом «количественного числа». Неинтерпретируемая система в данном случае - это аксиомы Пеано для системы счисления, трех примитивных идей и пяти аксиом которых, по мнению Пеано, было достаточно, чтобы можно было вывести все свойства системы натуральных чисел. На самом деле, утверждает Рассел, аксиомы Пеано определяют любое развитие формы из которых серия натуральных чисел является одним экземпляром.
  18. ^ Серый 2013, п. 133
    Итак, Пуанкаре обратился к вопросу, может ли логицизм порождать арифметику, точнее, арифметику ординалов. Кутюра, сказал Пуанкаре, принял аксиомы Пеано как определение числа. Но этого не пойдет. Невозможно доказать, что аксиомы свободны от противоречий, найдя их примеры, и любая попытка показать, что они свободны от противоречий, исследуя совокупность их импликаций, потребует самого принципа математической индукции, который, как полагал Кутюра, они подразумевали. Ибо (в следующем отрывке, опущенном из S&M) любой из них принимал принцип, чтобы доказать его, что доказывало бы только то, что, если оно истинно, оно не противоречит самому себе, что ничего не говорит; или кто-то использовал принцип в форме, отличной от указанной, и в этом случае нужно показать, что количество шагов в его рассуждениях было целым числом в соответствии с новым определением, но этого нельзя было сделать (1905c, 834).
  19. ^ Гильберт 1902.
  20. ^ Гёдель 1931.
  21. ^ Вольфрам, Стивен (2002). Новый вид науки. Wolfram Media, Inc. стр. 1152. ISBN  1-57955-008-8.
  22. ^ Гёдель 1958
  23. ^ Генцен 1936
  24. ^ Уиллард 2001.

Источники

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

внешняя ссылка

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