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

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

$\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) . Однако регулярность облегчает некоторых свойств ординалов доказательство ; и это позволяет проводить индукцию не только на хорошо упорядоченных множествах , но и на собственных классах, которые представляют собой хорошо обоснованные реляционные структуры, такие как лексикографическое упорядочение на $\{(n,\alpha )\mid n\in \omega \land \alpha {\text{ is an ordinal }}\}\,.$

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

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

последствия

Ни один набор не является самостоятельным элементом

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

Не существует бесконечной нисходящей последовательности наборов

Предположим, наоборот, что существует на натуральных функция 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 который также является элементом S. +1) , Итак, ( k +1 находится на пересечении f ) ( k ) и S. f Это противоречит тому факту, что они являются непересекающимися множествами. Поскольку наше предположение привело к противоречию, такой функции f не должно быть .

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

Обратите внимание, что этот аргумент применяется только к функциям f , которые могут быть представлены как множества, а не как неопределяемые классы. V Наследственно конечные множества ω _{удовлетворяют} аксиоме регулярности (и всем другим аксиомам ZFC, кроме аксиомы бесконечности ). Таким образом, если сформировать нетривиальную ультрастепень V _ω , то она также будет удовлетворять аксиоме регулярности. Результирующая модель будет содержать элементы, называемые нестандартными натуральными числами, которые удовлетворяют определению натуральных чисел в этой модели, но на самом деле не являются натуральными числами. . Это «поддельные» натуральные числа, которые «больше», чем любое реальное натуральное число. Эта модель будет содержать бесконечные нисходящие последовательности элементов. Например, предположим, что n — нестандартное натуральное число, тогда $(n-1)\in n$ и $(n-2)\in (n-1)$, и так далее. Для любого действительного натурального k числа $(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 , а именно $\textstyle \operatorname {rank} (w)=\cup \{\operatorname {rank} (z)+1\mid z\in w\}$. Это противоречит выводу о том, что w не имеет рейтинга. Таким образом, предположение о том, что u непусто, должно быть ложным и x должен иметь ранг.

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

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

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

Пусть непустое множество S является контрпримером к аксиоме регулярности; то есть каждый элемент S имеет непустое пересечение с S . Мы определяем бинарное отношение R на S следующим образом: $aRb:\Leftrightarrow b\in S\cap a$, которое по предположению является целым. Таким образом, согласно аксиоме зависимого выбора, существует некоторая последовательность ( an ₎ в S, a n _Ra n ₊₁ для всех n из N. удовлетворяющая Поскольку это бесконечная нисходящая цепочка, мы приходим к противоречию и, следовательно, такого S не существует.

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

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

иерархия и

В ZF можно доказать, что класс $\bigcup _{\alpha }V_{\alpha }$, называемая вселенной фон Неймана , равна классу всех множеств. Это утверждение даже эквивалентно аксиоме регулярности (если мы работаем в ZF без этой аксиомы). Из любой модели, не удовлетворяющей аксиоме регулярности, можно построить модель, удовлетворяющую ей, взяв только множества из $\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 в переводе), исключающую некоторые, но не все, необоснованные множества. В последующей публикации фон Нейман (1929 , стр. 231) дал эквивалентную, но более сложную версию аксиомы основания классов, ср. Суппес (1972 , стр. 53) и Леви (2002 , стр. 72):

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

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

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

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

См. также

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

Источники

• Бернейс, Пол Исаак (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, перепечатано в Булос, Джордж (1998), Логика, логика и логика , издательство Гарвардского университета, стр. 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), «Истоки бисимуляции и коиндукции», Санджорджи, Давиде; Руттен, Ян (ред.), « Продвинутые темы бисимуляции и коиндукции» , издательство Кембриджского университета
• Скотт, Дана Стюарт (1974), «Аксиоматизация теории множеств», Аксиоматическая теория множеств. Труды симпозиумов по чистой математике, том 13, часть II , стр. 207–214.
• Сколем, Торальф (1923), Аксиоматизированная теория множеств. Перепечатано в книге «От Фреге до Гёделя» , ван Хейеноорт, 1967, в английском переводе Стефана Бауэра-Менгельберга, стр. 291–301.
• Суппес, Патрик (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), «Аксиоматизация теории множеств», Журнал чистой и прикладной математики , 154 : 219–240 ; перевод на ван Хейеноорт, Жан (1967), От Фреге до Гёделя: справочник по математической логике, 1879–1931 , стр. 393–413
• фон Нейман, Джон (1928), «Об определении с помощью трансфинитной индукции и связанных с ней вопросах общей теории множеств», Mathematical Annals , 99 : 373–391, doi : 10.1007/BF01459102 , S2CID   120784562
• фон Нейман, Джон (1929), «К вопросу о непротиворечивости в аксиоматической теории множеств», Журнал чистой и прикладной математики , 1929 (160): 227–241, doi : 10.1515/crll.1929.160.227 , S2CID   199545822
• Цермело, Эрнст (1930), «О предельных числах и диапазонах множеств. Новые исследования основ теории множеств». (PDF) , Fundamenta Mathematicae , 16 : 29–47, doi : 10.4064/fm-16-1-29-47 , заархивировано (PDF) из оригинала 09 октября 2022 г .; перевод на Эвальд, ВБ, изд. (1996), От Канта до Гильберта: Справочник по основам математики, том. 2 , Clarendon Press, стр. 1219–33.

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

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