Аксиома регулярности - Axiom of regularity

В математике , то аксиома регулярности (также известный как аксиомой основания ) является аксиомой теории множеств Цермело-Френкеля , который гласит , что каждое непустое множество содержит элемент , который не пересекаются с A . В логике первого порядка аксиома гласит:

${\ displaystyle \ forall x \, (x \ neq \ varnothing \ rightarrow \ существует y (y \ in x \ \ land y \ cap x = \ varnothing)).}$

Аксиома регулярности вместе с аксиомой спаривания подразумевает, что никакое множество не является элементом самого себя и что не существует бесконечной последовательности ( a _n ) такой, что a _{i + 1} является элементом a _i для всех i . С помощью аксиомы зависимого выбора (которая является ослабленной формой аксиомы выбора ) этот результат может быть обращен вспять: если таких бесконечных последовательностей нет, то аксиома регулярности верна. Следовательно, в этом контексте аксиома регулярности эквивалентна предложению об отсутствии бесконечных нисходящих цепочек принадлежности.

Аксиома была введена фон Нейманом (1925) ; он был принят в формулировке, близкой к формулировке, найденной в современных учебниках Цермело (1930) . Практически все результаты в разделах математики, основанной на теории множеств, верны даже при отсутствии регулярности; см. главу 3 Кунена (1980) . Однако регулярность упрощает доказательство некоторых свойств ординалов ; и это позволяет проводить индукцию не только по хорошо упорядоченным множествам, но также и по соответствующим классам, которые являются хорошо обоснованными реляционными структурами, такими как лексикографический порядок на${\ displaystyle \ {(n, \ alpha) \ mid n \ in \ omega \ land \ alpha {\ text {является порядковым номером}} \} \ ,.}$

Учитывая другие аксиомы теории множеств Цермело – Френкеля, аксиома регулярности эквивалентна аксиоме индукции . Аксиома индукции обычно используется вместо аксиомы регулярности в интуиционистских теориях (те, которые не принимают закон исключенного среднего ), где две аксиомы не эквивалентны.

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

Элементарные следствия регулярности

Никакой набор не является элементом самого себя

Пусть A - множество, и применим аксиому регулярности к { A }, которая является множеством по аксиоме спаривания . Мы видим, что должен быть элемент из { A }, не пересекающийся с { A }. Поскольку единственный элемент в { A } - это A , должно быть, что A не пересекается с { A }. Итак, поскольку не может быть A ∈ A (по определению непересекающегося ). ${\ Displaystyle A \ cap \ {A \} = \ varnothing}$

Бесконечной убывающей последовательности наборов не существует

Предположим, напротив, что существует функция , е , на натуральных чисел с F ( п + 1) элемент ф ( п ) для каждого п . Определите S = { f ( n ): n натуральное число}, диапазон f , который можно увидеть как набор из схемы аксиомы замены . Применяя аксиому регулярности S , пусть В таком элементе S , который не пересекается с S . По определению S , B должно быть f ( k ) для некоторого натурального числа k . Тем не менее, мы , учитывая , что F ( K ) содержит п ( K + 1) , который также является элементом S . Таким образом , F ( K + 1) находится в пересечении с F ( K ) и S . Это противоречит тому факту, что они не пересекаются. Поскольку наше предположение привело к противоречию, такой функции f быть не должно .

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

Обратите внимание, что этот аргумент применяется только к функциям f, которые могут быть представлены как наборы, а не к неопределенным классам. В наследственно конечные множества , V _ω , удовлетворяют аксиоме регулярности (и все другие аксиомы ZFC , кроме аксиомы бесконечности ). Таким образом, если сформировать нетривиальную ультрастепень V _ω , то она также будет удовлетворять аксиоме регулярности. Результирующая модель будет содержать элементы, называемые нестандартными натуральными числами, которые удовлетворяют определению натуральных чисел в этой модели, но на самом деле не являются натуральными числами. Это поддельные натуральные числа, которые «больше» любого действительного натурального числа. Эта модель будет содержать бесконечные убывающие последовательности элементов. Например, предположим, что n - нестандартное натуральное число, затем и , и так далее. Для любого действительного натурального числа к , . Это бесконечная убывающая последовательность элементов. Но эта последовательность не может быть определена в модели и, следовательно, не является набором. Так что никакого противоречия с регулярностью доказать нельзя. ${\ Displaystyle (п-1) \ в п}$${\ Displaystyle (п-2) \ в (п-1)}$${\ Displaystyle (nk-1) \ in (nk)}$

Более простое теоретико-множественное определение упорядоченной пары

Аксиома регулярности позволяет определить упорядоченную пару ( a , b ) как { a , { a , b }}; подробности см. в заказанной паре . Это определение исключает одну пару фигурных скобок из канонического определения Куратовского ( a , b ) = {{ a }, { a , b }}.

Каждый набор имеет порядковый номер

Фактически это была первоначальная форма аксиомы в аксиоматизации фон Неймана.

Предположим, что x - произвольное множество. Пусть t - транзитивное замыкание { x }. Пусть u - подмножество t, состоящее из неранжированных множеств. Если u пусто, то ранжируется x, и все готово. В противном случае примените аксиому регулярности к u, чтобы получить элемент w из u, не пересекающийся с u . Поскольку w находится в u , w не имеет ранга. w является подмножеством t по определению транзитивного замыкания. Поскольку w не пересекается с u , каждый элемент w ранжируется. Применяя аксиомы замены и объединения для объединения рангов элементов w , мы получаем порядковый ранг для w , а именно . Это противоречит выводу о том, что w не имеет ранга. Таким образом, предположение, что u не пусто, должно быть ложным, а x должен иметь ранг. ${\ displaystyle \ textstyle \ operatorname {rank} (w) = \ cup \ {\ operatorname {rank} (z) +1 \ mid z \ in w \}}$

Для каждых двух наборов только один может быть элементом другого.

Пусть X и Y - множества. Затем примените аксиому регулярности к множеству { X , Y } (которое существует по аксиоме спаривания). Мы видим, что должен существовать элемент из { X , Y }, который также не пересекается с ним. Она должна быть либо X или Y . Тогда по определению дизъюнкта мы должны иметь либо, что Y не является элементом X, либо наоборот.

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

Пусть непустое множество S является контрпримером к аксиоме регулярности; то есть, каждый элемент из S имеет непустое пересечение с S . Определим бинарное отношение R на S путем , который весь по предположению. Таким образом, аксиомой зависимого выбора, существует некоторая последовательность ( _п ) в S , удовлетворяющая в _п Ra _{п + 1} для всех п в N . Поскольку это бесконечная убывающая цепочка, мы приходим к противоречию, и поэтому такой S не существует. ${\ displaystyle aRb: \ Leftrightarrow b \ in S \ cap a}$

Регулярность и остальные аксиомы ZF (C)

Сколем (1923) и фон Нейман (1929) показали, что регулярность относительно согласована с остальной частью ZF , что означает, что если ZF без регулярности согласован, то ZF (с регулярностью) также согласован. Его доказательство в современных обозначениях см. , Например, в Вооте (2001 , §10.1).

Также было показано, что аксиома регулярности независима от других аксиом ZF (C), если они непротиворечивы. Результат был объявлен Полом Бернейсом в 1941 году, хотя он не публиковал доказательства до 1954 года. Доказательство включает (и привело к изучению) перестановочные модели (или метод) Ригера-Бернейса , которые использовались для других доказательств независимости для необоснованные системы ( Rathjen 2004 , p. 193 и Forster 2003 , pp. 210–212).

Регулярность и парадокс Рассела

Наивная теория множеств (схема аксиом неограниченного понимания и аксиома экстенсиональности ) непоследовательна из-за парадокса Рассела . На ранних этапах формализации множеств математики и логики избегали этого противоречия, заменяя схему аксиом понимания гораздо более слабой схемой разделения аксиом . Однако один только этот шаг ведет к слишком слабым теориям множеств. Таким образом, некоторая сила понимания была добавлена ​​обратно через другие аксиомы существования теории множеств ZF (спаривание, объединение, набор степеней, замена и бесконечность), которые можно рассматривать как частные случаи понимания. Пока эти аксиомы, похоже, не приводят к противоречию. Впоследствии были добавлены аксиома выбора и аксиома регулярности, чтобы исключить модели с некоторыми нежелательными свойствами. Эти две аксиомы, как известно, относительно непротиворечивы.

При наличии схемы разделения аксиом парадокс Рассела становится доказательством того, что не существует множества всех множеств . Аксиома регулярности вместе с аксиомой спаривания также запрещают такое универсальное множество. Однако парадокс Рассела дает доказательство того, что не существует «множества всех множеств», использующих только схему аксиом разделения, без каких-либо дополнительных аксиом. В частности, ZF без аксиомы регулярности уже запрещает такое универсальное множество.

Если теория расширяется путем добавления аксиомы или аксиом, то любые (возможно, нежелательные) следствия исходной теории остаются следствиями расширенной теории. В частности, если ZF без регулярности расширяется путем добавления регулярности, чтобы получить ZF, то любое противоречие (например, парадокс Рассела), которое следует из исходной теории, все равно будет следовать в расширенной теории.

Существование атомов Куайна (множества, которые удовлетворяют формуле уравнения x  = { x }, т. Е. Сами являются их единственными элементами) согласуется с теорией, полученной удалением аксиомы регулярности из ZFC. Различные необоснованные теории множеств допускают «безопасные» круговые множества, такие как атомы Куайна, не становясь противоречивыми посредством парадокса Рассела.

Регулярность, совокупная иерархия и типы

В ZF можно доказать, что класс , называемый вселенной фон Неймана , равен классу всех множеств. Это утверждение даже эквивалентно аксиоме регулярности (если мы работаем в ZF без этой аксиомы). Из любой модели, которая не удовлетворяет аксиоме регулярности, модель, которая ей удовлетворяет, может быть построена путем взятия только множеств . ${\ displaystyle \ bigcup _ {\ alpha} V _ {\ alpha}}$${\ displaystyle \ bigcup _ {\ alpha} V _ {\ alpha}}$

Герберт Эндертон  ( 1977 , стр. 206) писал, что «идея ранга является потомком концепции типа Рассела ». Сравнивая ZF с теорией типов , Аласдер Уркхарт писал, что «система Цермело имеет то преимущество, что не содержит явно типизированных переменных, хотя на самом деле ее можно рассматривать как имеющую встроенную неявную структуру типов, по крайней мере, если аксиома регулярности такова. Подробности этой неявной типизации изложены в [Zermelo 1930] и снова в известной статье Джорджа Булоса [Boolos 1971] ».

Дана Скотт  ( 1974 ) пошла дальше и утверждала, что:

Истина в том, что есть только один удовлетворительный способ избежать парадоксов: а именно использование некоторой формы теории типов . Это лежало в основе интуиции Рассела и Цермело. Действительно, лучше всего рассматривать теорию Цермело как упрощение и расширение теории Рассела. (Мы , конечно, имеем в виду простую теорию типов Рассела .) Упрощение заключалось в том, чтобы сделать типы кумулятивными . Таким образом упрощается смешивание типов и избегается надоедливое повторение. Как только последним типам будет позволено накапливать более ранние, мы сможем легко представить расширение типов в трансфинитное - вопрос о том, насколько далеко мы хотим зайти, обязательно должен оставаться открытым. Теперь Рассел сделал свои типы явными в своих обозначениях, а Цермело оставил их неявными . [курсив в оригинале]

В той же статье Скотт показывает, что аксиоматическая система, основанная на внутренних свойствах совокупной иерархии, оказывается эквивалентной ZF, включая регулярность.

История

Понятия обоснованности и ранга множества были введены Дмитрием Миримановым ( 1917 ) ср. Леви (2002 , с. 68) и Халлетт (1996 , §4.4, особенно с. 186, 188). Мириманов назвал множество x «правильным» (французский: «ordinaire»), если каждая нисходящая цепь x ∋ x ₁ ∋ x ₂ ∋ ... конечна. Мириманов, однако, не считал свое понятие регулярности (и обоснованности) аксиомой, которую должны соблюдать все группы; в более поздних статьях Мириманов также исследовал то, что сейчас называется необоснованными множествами («экстраординарными» в терминологии Мириманова).

Сколем (1923) и фон Нейман (1925) указали, что необоснованные множества излишни (на стр. 404 в переводе ван Хейенорта ), и в той же публикации фон Нейман приводит аксиому (стр. 412 в переводе), исключающую некоторые, но не все, необоснованные множества. В последующей публикации фон Нейман (1928) дал следующую аксиому (переведенную в современных обозначениях А. Ригером):

${\ displaystyle \ forall x \, (x \ neq \ emptyset \ rightarrow \ существует y \ in x \, (y \ cap x = \ emptyset))}$.

Регулярность наличия мочевых элементов

Урэлементы - это объекты, которые не являются наборами, но могут быть элементами наборов. В теории множеств ZF нет элементов, но в некоторых других теориях множеств, таких как ZFA , они есть. В этих теориях аксиома регулярности должна быть изменена. Оператор " " необходимо заменить оператором, который не является пустым и не является элементом urelement. Одной подходящей замены , в котором говорится , что х является заселена . ${\ Displaystyle х \ neq \ emptyset}$${\ displaystyle x}$${\ Displaystyle (\ существует у) [у \ в х]}$

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

• Необоснованная теория множеств
• Уловка Скотта
• Эпсилон-индукция

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

Источники

• Bernays, Пол Исаак (1941), "Система аксиоматической теории множеств Часть II.", Журнал символической логики , 6 (1): 1-17, DOI : 10,2307 / 2267281 , JSTOR  2267281
• Bernays, Пол Исаак (1954), "система аксиоматической теории множеств Часть VII." (PDF) , Журнал символической логики , 19 (2): 81-96, DOI : 10,2307 / 2268864 , JSTOR  2268864
• Boolos, Джордж (1971), "Итерационный концепция множества", журнал философии , 68 (8): 215-231, DOI : 10,2307 / 2025204 , JSTOR  2025204перепечатано в Boolos, George (1998), Logic, Logic and Logic , Harvard University Press, стр. 13–29
• Эндертон, Герберт Б. (1977), Элементы теории множеств , Academic Press
• Форстер, Т. (2003), Логика, индукция и множества , Cambridge University Press
• Хальбайзен, Лоренц Дж. (2012), Комбинаторная теория множеств: с мягким введением в принуждение , Springer
• Халлетт, Майкл (1996) [впервые опубликовано в 1984 году], теория канторовских множеств и ограничение размера , Oxford University Press, ISBN 978-0-19-853283-5
• Jech, Thomas (2003), Теория множеств: издание третьего тысячелетия, пересмотренное и расширенное , Springer, ISBN 978-3-540-44085-7
• Кунен, Кеннет (1980), Теория множеств: Введение в доказательства независимости , Elsevier, ISBN 978-0-444-86839-8
• Леви, Азриэль (2002) [впервые опубликовано в 1979 году], Базовая теория множеств , Минеола, Нью-Йорк: Dover Publications, ISBN 978-0-486-42079-0
• Мириманофф, Д. (1917), "Антиномии Рассела и Бурали-Форти и основная проблема теории ансамблей", L'Enseignement Mathématique , 19 : 37–52
• Ратьен, М. (2004), « Предсказуемость, круговорот и анти-основание» (PDF) , в Линке, Годехарде (ред.), « Сто лет парадокса Рассела: математика, логика, философия» , Уолтер де Грюйтер, ISBN 978-3-11-019968-0
• Ригер, Адам (2011), «Парадокс, ZF и аксиома основания» (PDF) , в ДеВиди, Дэвид; Халлетт, Майкл; Кларк, Питер (ред.), Логика, математика, философия, старинные энтузиазмы. Очерки в честь Джона Л. Белла. , Серия Western Ontario по философии науки, 75 , стр. 171–187, CiteSeerX  10.1.1.100.9052 , DOI : 10.1007 / 978-94-007-0214-1_9 , ISBN 978-94-007-0213-4
• Riegger, L. (1957), "Вклад в аксиоматической теории множеств Гёделя" (PDF) , Чехословацкий математический журнал , 7 (3): 323-357, DOI : 10,21136 / CMJ.1957.100254
• Sangiorgi, Davide (2011), «Истоки бисимуляции и коиндукции», в Sangiorgi, Davide; Руттен, Ян (ред.), Advanced Topics in Bisimulation and Coinduction , Cambridge University Press
• Скотт, Дана Стюарт (1974), "Аксиоматизирующая теория множеств", Аксиоматическая теория множеств. Труды симпозиумов по чистой математике, том 13, часть II , стр. 207–214
• Сколем, Торальф (1923), аксиоматизированная теория множествПерепечатано в « From Frege to Gödel» , van Heijenoort, 1967, в английском переводе Стефана Бауэра-Менгельберга, стр. 291–301.
• Уркхарт, Аласдер (2003), «Теория типов», Гриффин, Николас (редактор), Кембриджский компаньон Бертрана Рассела , Cambridge University Press
• Воот, Роберт Л. (2001), Теория множеств: Введение (2-е изд.), Springer, ISBN 978-0-8176-4256-3
• фон Нейман, Джон (1925), "Eine axiomatiserung der Mengenlehre", Journal für die Reine und Angewandte Mathematik , 154 : 219–240; перевод Ван Хейеноорта, Жан (1967), От Фреге до Гёделя: Справочник по математической логике, 1879–1931 , стр. 393–413
• фон Неймана, Джон (1928), "Определение матрицы Убер Durch трансфинитная Induktion унд verwandte Fragen дер Allgemeinen Mengenlehre", Mathematische Annalen , 99 : 373-391, DOI : 10.1007 / BF01459102 , S2CID  120784562
• фон Нейман, Джон (1929), "Uber eine Widerspruchfreiheitsfrage in der axiomatischen Mengenlehre", Journal für die Reine und Angewandte Mathematik , 1929 (160): 227–241, doi : 10.1515 / crll.1929.160.227 , S2CID  199545822
• Цермело, Эрнст (1930), «Über Grenzzahlen und Mengenbereiche. Neue Untersuchungen über die Grundlagen der Mengenlehre». (PDF) , Fundamenta Mathematicae , 16 : 29-47, DOI : 10,4064 / FM-16-1-29-47; перевод в Эвальде, WB, изд. (1996), От Канта до Гильберта: Справочник по основам математики Vol. 2 , Clarendon Press, стр. 1219–33

Внешние ссылки

• Аксиома основания в PlanetMath .
• Жилой комплекс и аксиома основания на nLab