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

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

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

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

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

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

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

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

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

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

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

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

Обратите внимание, что этот аргумент применяется только к функциям ж которые могут быть представлены как множества, а не как неопределимые классы. В наследственно конечные множества, Vω, удовлетворяют аксиоме регулярности (и всем другим аксиомам ZFC кроме аксиома бесконечности ). Итак, если сформировать нетривиальный сверхмощный из Vω, то оно также будет удовлетворять аксиоме регулярности. Результирующий модель будет содержать элементы, называемые нестандартными натуральными числами, которые удовлетворяют определению натуральных чисел в этой модели, но на самом деле не являются натуральными числами. Это поддельные натуральные числа, которые «больше» любого действительного натурального числа. Эта модель будет содержать бесконечные убывающие последовательности элементов. Например, предположим п нестандартное натуральное число, то и , и так далее. Для любого действительного натурального числа k, . Это бесконечная убывающая последовательность элементов. Но эта последовательность не определяется в модели и, следовательно, не является набором. Так что никакого противоречия с регулярностью доказать нельзя.

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

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

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

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

Предполагать Икс есть любой набор. Позволять т быть переходное закрытие из {Икс}. Позволять ты быть подмножеством т состоящий из нерейтинговых сетов. Если ты пусто, то Икс ранжируется, и мы закончили. В противном случае примените аксиому регулярности к ты получить элемент ш из ты который не пересекается с ты. С ш в ты, ш не имеет рейтинга. ш это подмножество т по определению транзитивного замыкания. С ш не пересекается с ты, каждый элемент ш ранжируется. Применяя аксиомы замены и объединения, чтобы объединить ряды элементов ш, получаем порядковый номер для ш, а именно . Это противоречит заключению, что ш не имеет рейтинга. Итак, предположение, что ты не было пустым, должно быть ложным и Икс должен иметь звание.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

История

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

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

.

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

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

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

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

  1. ^ Ригер 2011, pp. 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, Дои:10.2307/2267281, JSTOR  2267281
  • Бернейс, Пол Исаак (1954), «Система аксиоматической теории множеств. Часть VII» (PDF), Журнал символической логики, 19 (2): 81–96, Дои:10.2307/2268864, JSTOR  2268864
  • Булос, Джордж (1971), «Итеративная концепция множества», Журнал Философии, 68 (8): 215–231, Дои:10.2307/2025204, JSTOR  2025204 перепечатано в Булос, Джордж (1998), Логика, логика и логика, Harvard University Press, стр. 13–29.
  • Эндертон, Герберт Б. (1977), Элементы теории множеств, Academic Press
  • Форстер, Т. (2003), Логика, индукция и множества, Издательство Кембриджского университета
  • Хальбайзен, Лоренц Дж. (2012), Комбинаторная теория множеств: мягкое введение в принуждение, Springer
  • Халлетт, Майкл (1996) [впервые опубликовано в 1984 году], Канторовская теория множеств и ограничение размера, Издательство Оксфордского университета, ISBN  978-0-19-853283-5
  • Jech, Thomas (2003), Теория множества: издание третьего тысячелетия, переработанное и дополненное, Спрингер, ISBN  978-3-540-44085-7
  • Кунен, Кеннет (1980), Теория множеств: введение в доказательства независимости, Эльзевьер, 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), в Link, Годехард (ред.), Сто лет парадокса Рассела: математика, логика, философия, Вальтер де Грюйтер, ISBN  978-3-11-019968-0
  • Ригер, Адам (2011), «Парадокс, ZF и аксиома основания» (PDF)в ДеВиди, Дэвид; Халлетт, Майкл; Кларк, Питер (ред.), Логика, математика, философия, старинные увлечения. Очерки в честь Джона Л. Белла., Серия "Западный Онтарио" по философии науки, 75, стр. 171–187, CiteSeerX  10.1.1.100.9052, Дои:10.1007/978-94-007-0214-1_9, ISBN  978-94-007-0213-4
  • Риггер, Л. (1957), «Вклад в аксиоматическую теорию множеств Гёделя» (PDF), Чехословацкий математический журнал, 7 (3): 323–357, Дои:10.21136 / CMJ.1957.100254
  • Sangiorgi, Davide (2011), «Истоки бисимуляции и коиндукции», в Sangiorgi, Davide; Руттен, Ян (ред.), Продвинутые темы по бисимуляции и коиндукции, Издательство Кембриджского университета
  • Скотт, Дана Стюарт (1974), "Аксиоматизирующая теория множеств", Аксиоматическая теория множеств. Труды симпозиумов по чистой математике Том 13, Часть II, стр. 207–214
  • Сколем, Торальф (1923), Аксиоматизированная теория множествCS1 maint: ref = harv (связь) Перепечатано в От Фреге до Гёделя, van Heijenoort, 1967, в английском переводе Стефана Бауэра-Менгельберга, стр. 291–301.
  • Уркхарт, Аласдер (2003), «Теория типов», в Гриффине, Николас (ред.), Кембриджский компаньон Бертрана Рассела, Издательство Кембриджского университета
  • Воот, Роберт Л. (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), "Uber die Definition durch transfinite Induktion und verwandte Fragen der allgemeinen Mengenlehre", Mathematische Annalen, 99: 373–391, Дои: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, Дои:10.1515 / crll.1929.160.227, S2CID  199545822
  • Цермело, Эрнст (1930), "Uber Grenzzahlen und Mengenbereiche. Neue Untersuchungen über die Grundlagen der Mengenlehre." (PDF), Fundamenta Mathematicae, 16: 29–47, Дои:10.4064 / fm-16-1-29-47; перевод на Эвальд, У.Б., изд. (1996), От Канта до Гильберта: Справочник по основам математики Vol. 2, Clarendon Press, стр. 1219–33

внешняя ссылка