Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Аксиома была введена фон Нейманом (1925) ; он был принят в формулировке, близкой к формулировке, найденной в современных учебниках Цермело (1930) . Практически все результаты в разделах математики, основанной на теории множеств, верны даже при отсутствии регулярности; см. главу 3 Кунена (1980) . Однако регулярность упрощает доказательство некоторых свойств ординалов ; и это позволяет не только индукционный сделать на вполне упорядоченные множествах , но и на собственных классах, которые хорошо обоснованных реляционные структуры , такие как лексикографическое упорядочение на

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

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

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

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

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

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

Предположим, напротив, что существует функция , е , на натуральных чисел с 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 - нестандартное натуральное число, затем и , и так далее. Для любого действительного натурального числа к , . Это бесконечная убывающая последовательность элементов. Но эта последовательность не определяется в модели и, следовательно, не является набором. Так что никакого противоречия с регулярностью доказать нельзя.

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

Аксиома регулярности позволяет определить упорядоченную пару ( 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 должен иметь ранг.

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

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

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

Пусть непустое множество S является контрпримером к аксиоме регулярности; то есть, каждый элемент из S имеет непустое пересечение с S . Определим бинарное отношение R на S путем , который весь по предположению. Таким образом, аксиомой зависимого выбора, существует некоторая последовательность ( п ) в S , удовлетворяющая в п Ra п + 1 для всех п в N . Поскольку это бесконечная убывающая цепочка, мы приходим к противоречию, и поэтому такой S не существует.

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

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

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

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

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

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

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

История [ править ]

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

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

.

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

Урэлементы - это объекты, которые не являются наборами, но могут быть элементами наборов. В теории множеств ZF нет элементов, но в некоторых других теориях множеств, таких как ZFA , они есть. В этих теориях аксиома регулярности должна быть изменена. Оператор " " необходимо заменить оператором, который не является пустым и не является элементом urelement. Одной подходящей замены , в котором говорится , что х является заселена .

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Rieger 2011 , стр. 175178.
  2. Перейти ↑ Urquhart 2003 , p. 305.
  3. ↑ Леви, 2002 , с. 73.
  4. ^ Halbeisen 2012 , стр. 62-63.
  5. ^ Sangiorgi 2011 , стр. 17-19, 26.
  6. Перейти ↑ Rieger 2011 , p. 179.

Источники [ править ]

  • 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, Томас (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) , в ДеВиди, Дэвид; Халлетт, Майкл; Кларк, Питер (ред.), Логика, математика, философия, старинные энтузиазмы. Очерки в честь Джона Л. Белла. , The Western Ontario Series in Philosophy of Science, 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