Аксиома регулярности

Аксиома теории множеств

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

${\displaystyle \forall x\,(x\neq \varnothing \rightarrow \exists 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{ is an ordinal }}\}\,.}$

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

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

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

Ни одно множество не является элементом самого себя.

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

Не существует бесконечной убывающей последовательности множеств.

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

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

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

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

Аксиома регулярности позволяет определить упорядоченную пару ( 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 с помощью , которое является целым по предположению. Таким образом, по аксиоме зависимого выбора существует некоторая последовательность ( a _n ) в S , удовлетворяющая a _n Ra _n+1 для всех n из N . Поскольку это бесконечная нисходящая цепочка, мы приходим к противоречию, и, следовательно, такого S не существует. ${\displaystyle aRb:\Leftrightarrow b\in S\cap a}$

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

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

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

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

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

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

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

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

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

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

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

Дэна Скотт  (1974) пошёл дальше и заявил, что:

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

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

История

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

Скулем (1923) и фон Нейман (1925) указали, что не вполне обоснованные множества являются избыточными (на стр. 404 в переводе ван Хейеноорта), и в той же публикации фон Нейман приводит аксиому (стр. 412 в переводе), которая исключает некоторые, но не все, не вполне обоснованные множества. ^[6] В последующей публикации фон Нейман (1929, стр. 231) привел эквивалентную, но более сложную версию аксиомы основания классов, см. Suppes (1972, стр. 53) и Lévy (2002, стр. 72):

${\displaystyle A\neq \emptyset \rightarrow \exists x\in A\,(x\cap A=\emptyset )}$.

Современная и окончательная форма аксиомы принадлежит Цермело (1930).

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

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

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

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

Ссылки

1. Ригер 2011, стр. 175, 178.
2. Уркухарт 2003, стр. 305.
3. Леви 2002, стр. 73.
4. Halbeisen 2012, стр. 62–63.
5. Санджорджи 2011, стр. 17–19, 26.
6. Ригер 2011, стр. 179.

Источники

• Бернайс, Пол Айзек (1941), «Система аксиоматической теории множеств. Часть II», The Journal of Symbolic Logic , 6 (1): 1–17, doi :10.2307/2267281, JSTOR  2267281, S2CID  250344277
• Бернайс, Пол Айзек (1954), «Система аксиоматической теории множеств. Часть VII» (PDF) , The Journal of Symbolic Logic , 19 (2): 81–96, doi :10.2307/2268864, JSTOR  2268864, S2CID  250351655
• Булос, Джордж (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
• Йех, Томас (2003), Теория множеств: издание третьего тысячелетия, исправленное и расширенное , Springer, ISBN 978-3-540-44085-7
• Кунен, Кеннет (1980), Теория множеств: Введение в доказательства независимости , Elsevier, ISBN 978-0-444-86839-8
• Lévy, Azriel (2002) [впервые опубликовано в 1979], Basic set theory , Mineola, New York: Dover Publications, ISBN 978-0-486-42079-0
• Мириманов, Дмитрий (1917), «Антиномии Рассела и Бурали-Форти и фундаментальные проблемы теории ансамблей», L'Enseignement Mathématique , 19 : 37–52
• Ратьен, М. (2004), «Предикативность, кругообразность и антиоснование» (PDF) , в Link, Godehard (ред.), Сто лет парадокса Рассела: математика, логика, философия , Вальтер де Грюйтер, ISBN 978-3-11-019968-0, архив (PDF) из оригинала 2022-10-09
• Ригер, Адам (2011), «Парадокс, ZF и аксиома основания» (PDF) , в ДеВиди, Дэвид; Халлетт, Майкл; Кларк, Питер (ред.), Логика, Математика, Философия, Винтажные Энтузиазмы. Эссе в честь Джона Л. Белла. , Серия Западного Онтарио по философии науки, т. 75, стр. 171–187, CiteSeerX  10.1.1.100.9052 , doi :10.1007/978-94-007-0214-1_9, ISBN 978-94-007-0213-4
• Риггер, Л. (1957), «Вклад в аксиоматическую теорию множеств Гёделя» (PDF) , Czechoslovak Mathematical Journal , 7 (3): 323–357, doi : 10.21136/CMJ.1957.100254
• Санджорджи, Давиде (2011), «Истоки бисимуляции и коиндукции», в Санджорджи, Давиде; Раттен, Ян (ред.), Расширенные темы бисимуляции и коиндукции , Cambridge University Press
• Скотт, Дана Стюарт (1974), "Аксиоматизация теории множеств", Аксиоматическая теория множеств. Труды симпозиумов по чистой математике, том 13, часть II , стр. 207–214
• Сколем, Торальф (1923), Аксиоматизированная теория множествПерепечатано в книге «От Фреге до Гёделя» , ван Хейеноорт, 1967, в английском переводе Стефана Бауэра-Менгельберга, стр. 291–301.
• Suppes, Patrick (1972) [впервые опубликовано в 1960], Аксиоматическая теория множеств , Dover Publications, Inc., ISBN 978-0-486-61630-8
• Уркухарт, Аласдер (2003), «Теория типов», в Гриффин, Николас (ред.), Кембриджский компаньон Бертрана Рассела , Cambridge University Press
• Воот, Роберт Л. (2001), Теория множеств: Введение (2-е изд.), Springer, ISBN 978-0-8176-4256-3
• фон Нейман, Джон (1925), «Eine Axiomatisierung der Mengenlehre», Journal für die Reine und Angewandte Mathematik , 154 : 219–240; перевод в van Heijenoort, Jean (1967), От Фреге к Гёделю: Справочник по математической логике, 1879–1931 , стр. 393–413
• фон Нейман, Джон (1928), «Über die Definition durch transfinite Induktion und verwandte Fragen der 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 , заархивировано (PDF) из оригинала 9 октября 2022 г.; перевод в Ewald, WB, ed. (1996), От Канта до Гильберта: Учебник по основам математики, том 2 , Clarendon Press, стр. 1219–33

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

• Аксиома основания в PlanetMath .
• Обитаемое множество и аксиома основания на nLab