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

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

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

${\displaystyle \forall x\,(x\neq \varnothing \rightarrow \exists y(y\in x\ \land y\cap x=\varnothing )).}$

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

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

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

Также было показано, что аксиома регулярности независима от других аксиом ZF(C) при условии их непротиворечивости. Результат был объявлен Полом Бернейсом в 1941 году, хотя он не публиковал доказательство до 1954 года. Доказательство включает в себя (и привело к изучению) модели (или метод) перестановок Ригера-Бернейса, которые использовались для других доказательств независимости необоснованные системы (Ратьен 2004, стр. 193 и Форстер 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] в более поздних работах Мириманов также исследовал то, что сейчас называется необоснованными множествами («экстраординарными» в терминологии Мириманова). ^[5]

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

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

Закономерность при наличии урелементов

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

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

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

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

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

Источники

• Бернейс, Пол Исаак (1941), «Система аксиоматической теории множеств. Часть II», Журнал символической логики , 6 (1): 1–17, doi : 10.2307/2267281, JSTOR  2267281, S2CID  250344277
• Бернейс, Пол Исаак (1954), «Система аксиоматической теории множеств. Часть VII» (PDF) , Журнал символической логики , 19 (2): 81–96, doi : 10.2307/2268864, JSTOR  2268864, S2CID  250351655
• Булос, Джордж (1971), «Итеративная концепция множества», Journal of Philosophy , 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
• Леви, Азриэль (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, заархивировано (PDF) из оригинала 9 октября 2022 г.
• Ригер, Адам (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) , Чехословацкий математический журнал , 7 (3): 323–357, doi : 10.21136/CMJ.1957.100254
• Санджорджи, Давиде (2011), «Истоки бисимуляции и коиндукции», Санджорджи, Давиде; Руттен, Ян (ред.), « Продвинутые темы бисимуляции и коиндукции» , издательство Cambridge University Press
• Скотт, Дана Стюарт (1974), «Аксиоматизация теории множеств», Аксиоматическая теория множеств. Труды симпозиумов по чистой математике, том 13, часть II , стр. 207–214.
• Сколем, Торальф (1923), Аксиоматизированная теория множествПерепечатано в книге «От Фреге до Гёделя» , ван Хейенорт, 1967, в английском переводе Стефана Бауэра-Менгельберга, стр. 291–301.
• Уркхарт, Аласдер (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; перевод в ван Хейеноорте, Жане (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 г.; перевод в Эвальде, ВБ, изд. (1996), От Канта до Гильберта: Справочник по основам математики, том. 2 , Clarendon Press, стр. 1219–33.

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

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