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


Из Википедии, свободной энциклопедии

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

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

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

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

Когда Пеано сформулировал свои аксиомы, язык математической логики был в зачаточном состоянии. Система логических обозначений он создан , чтобы представить аксиомы не оказаться популярными, хотя он был генезисом современной нотации для множества членов (Е, который исходит от й Пеан) и косвенно (⊃, который исходит от Пеано вспять " . с») Пеано поддерживается четкое различие между математическими и логическими символами, которые еще не были распространены в математике; такое разделение было впервые введено в Begriffsschrift по Фрегу , опубликованном в 1879. Пеано не знали о работе Фрега и независимо воссоздала его логическое устройство на основе работы Буля и Шредер .

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

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

  1. 0 представляет собой натуральное число.

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

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

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

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

Первоначальная формулировка Пеано аксиом используется 1 вместо 0 в качестве «первого» натурального числа. Этот выбор является произвольным, поскольку аксиома 1 не наделяет константу 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 ,
    то К содержит все натуральное число.

Индукционная аксиома иногда указывается в следующем виде:

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

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

арифметика

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

прибавление

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

Например:

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

умножение

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

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

· S (0) = а + ( · 0) = а + 0 = а ,

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

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

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

· ( Ь + с ) = ( · б ) + ( · с ).

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

Неравенства

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

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

Это соотношение является стабильным относительно сложения и умножения: для , если б , то:

  • + сЬ + с , и
  • · сЬ · с .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

модели

Модель аксиом Пеано является тройной ( N , 0, S ) , где N является (необязательно бесконечное) множество, 0 ∈ N и S  : NN удовлетворяет аксиомам выше. Дедекиндово доказал в своей 1888 года книге, характер и значение чисел ( немецкий : Был ли Синд унд был Sollen умереть ZAHLEN , то есть «? Какие цифры и что они хороши») , что любые две модели аксиом Пеано ( в том числе второго порядка аксиомы индукции) являются изоморфными . В частности, даны две модели ( N A , 0 , S ) и ( N B , 0 B , S Б ) из аксиом Пеано, существует единственный гомоморфизм F  : NN B , удовлетворяющих

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

Набор Теоретико-модели

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

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

и так далее. Множество Н вместе с 0 , а функция правопреемника с  : NN удовлетворяет аксиомы Пеано.

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

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

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

  • Объекты США 1 ( C ) являются тройки ( X , 0 X , S Х ) , где Х является объектом C и 0 X  : 1 СX и S X  : XX являются C -morphisms.
  • Морфизмом φ  : ( Х , 0 Х , S Х ) → ( Y , 0 Y , S Y ) является С -морфизмом φ  : XY с ф 0 X = 0 Y и φ S X = S Y ф .

Тогда С называются удовлетворяют аксиомы Дедекинда Пеано , если США 1 ( С ) имеет начальный объект; Этот исходный объект известен как природный объект числа в C . Если ( N , 0, S ) этот исходный объект, и ( х , 0 Х , S Х ) является любой другой объект, то единственное отображение у  : ( N , 0, S ) → ( Х , 0 Х , S Х ) такова , что

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

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

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

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

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

то, что пролито

Разрез в нестандартной модели M является непустым подмножеством Я из М так , что я направлен вниз замкнутый ( х < у и уI означает еI ) и I замкнут относительно преемника. Собственно разрез является разрезом , который является подмножеством M . Каждая нестандартная модель имеет много правильных сокращений, в том числе тот , который соответствует стандарту натуральных чисел. Тем не менее, схема индукции в арифметике Пеано предотвращает надлежащее сокращение от быть определимы. Перелива лемма доказана впервые Abraham Robinson, формализует этот факт.

Сверхпролитие Лемма Пусть M является нестандартной моделью ПА и пусть я быть собственным кроем М . Предположим , что такой набор элементов М и представляет собой формулу в языке арифметики , так что
для всех ЬI .
Тогда существует с в М , которое больше , чем каждый элемент I такой , что

консистенция

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

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

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

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

Заметки

Цитирование

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

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

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

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