Ультрафильтр

В математической области теории порядка — ультрафильтр на заданном частично упорядоченном множестве (или «ЧУУ») ${\textstyle P}$ представляет собой определенное подмножество $P,$ а именно максимальный фильтр на $P;$ то есть правильный фильтр на ${\textstyle P}$ который нельзя увеличить до более крупного правильного фильтра на $P.$

Если $X$ — произвольное множество, его степенное множество ${\mathcal {P}}(X),$ упорядоченный включением множества , всегда является булевой алгеброй и, следовательно, частично упорядоченным множеством, а также ультрафильтрами на ${\mathcal {P}}(X)$ обычно называются ультрафильтрами на множестве $X$ . ^{[примечание 1]} Ультрафильтр в комплекте $X$ можно рассматривать как конечно-аддитивную 0-1-значную меру на ${\mathcal {P}}(X)$ . С этой точки зрения каждое подмножество $X$ считается либо « почти всем » (имеет меру 1), либо «почти ничем» (имеет меру 0), в зависимости от того, принадлежит оно данному ультрафильтру или нет. ^[1]^: §4

Ультрафильтры имеют множество приложений в теории множеств, теории моделей , топологии. ^[2]^: 186 и комбинаторика. ^[3]

Ультрафильтры по частичным заказам

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

Формально, если ${\textstyle P}$ представляет собой набор, частично упорядоченный по $\,\leq \,$ затем

подмножество $F\subseteq P$ $F\subseteq P$ называется фильтром на ${\textstyle P}$ ${\текстовый стиль П}$ если
- $F$ непусто,
- для каждого $x,y\in F,$ существует некоторый элемент $z\in F$ такой, что $z\leq x$ и $z\leq y,$ и
- для каждого $x\in F$ и $y\in P,$ $x\leq y$ подразумевает, что $y$ находится в $F$ слишком;
подмножество правильное $U$ $U$ из ${\textstyle P}$ ${\текстовый стиль П}$ называется ультрафильтром ${\textstyle P}$ ${\текстовый стиль П}$ если
- $U$ это фильтр на $P,$ и
- нет подходящего фильтра $F$ на ${\textstyle P}$ который правильно расширяет $U$ (то есть такой, что $U$ является правильным подмножеством $F$ ).

Виды и существование ультрафильтров

Каждый ультрафильтр попадает ровно в одну из двух категорий: основной или свободный. Главный наименьший (или фиксированный , или тривиальный ) ультрафильтр — это фильтр, содержащий элемент . Следовательно, каждый главный ультрафильтр имеет вид $F_{p}=\{x:p\leq x\}$ для какого-то элемента $p$ данного ч.у.м. В этом случае $p$ называется главным элементом ультрафильтра. Любой ультрафильтр, не являющийся главным, называется свободным (или неглавным ) ультрафильтром. Для произвольного $p$ , набор $F_{p}$ представляет собой фильтр, называемый основным фильтром в $p$ ; он является главным ультрафильтром только в том случае, если он максимален.

Для ультрафильтров на силовом агрегате ${\mathcal {P}}(X),$ главный ультрафильтр состоит из всех подмножеств $X$ которые содержат данный элемент $x\in X.$ Каждый ультрафильтр на ${\mathcal {P}}(X)$ это тоже главный фильтр такой формы. ^[2]^: 187 Поэтому ультрафильтр $U$ на ${\mathcal {P}}(X)$ является главным тогда и только тогда, когда оно содержит конечное множество. ^{[примечание 2]} Если $X$ бесконечен, ультрафильтр $U$ на ${\mathcal {P}}(X)$ следовательно, неглавен тогда и только тогда, когда он содержит Фреше коконитых подмножеств фильтр $X.$ ^{[примечание 3]}^[4]^{: Предложение 3} Если $X$ конечен, каждый ультрафильтр является главным. ^[2]^: 187 Если $X$ бесконечен, то фильтр Фреше не является ультрафильтром на степенном наборе $X$ но это ультрафильтр на конечно-коконитной алгебре $X.$

Каждый фильтр в булевой алгебре (или, в более общем плане, любое подмножество со свойством конечного пересечения ) содержится в ультрафильтре (см. лемму об ультрафильтре ), и поэтому существуют свободные ультрафильтры, но доказательства включают аксиому выбора ( AC ) в форме Лемма Цорна . С другой стороны, утверждение, что каждый фильтр содержится в ультрафильтре, не подразумевает AC . Действительно, это эквивалентно булевой теореме о простых идеалах ( BPIT ), хорошо известной промежуточной точке между аксиомами теории множеств Цермело–Френкеля ( ZF ) и теорией ZF, дополненной аксиомой выбора ( ZFC ). В общем, доказательства, включающие аксиому выбора, не дают явных примеров свободных ультрафильтров, хотя явные примеры можно найти в некоторых моделях ZFC ; например, Гёдель показал, что это можно сделать в конструируемой вселенной , где можно записать явную глобальную функцию выбора. В ZF без аксиомы выбора возможно, что каждый ультрафильтр будет главным. ^[5]

Ультрафильтр на булевой алгебре

Важный частный случай понятия возникает, если рассматриваемое ЧУ-множество является булевой алгеброй . При этом ультрафильтры характеризуются содержанием для каждого элемента $x$ булевой алгебры ровно один из элементов $x$ и $\lnot x$ (последнее является логическим дополнением $x$ ):

Если ${\textstyle P}$ является булевой алгеброй и $F$ это правильный фильтр на $P,$ то следующие утверждения эквивалентны:

$F$ это ультрафильтр на $P,$
$F$ является фильтром простого действия на $P,$
для каждого $x\in P,$ или $x\in F$ или ( $\lnot x$ ) $\in F.$ ^[2]^: 186

Доказательство эквивалентности 1 и 2 также приведено в (Burris, Sankappanavar, 2012, следствие 3.13, стр. 133). ^[6]

Более того, ультрафильтры на булевой алгебре могут быть связаны с максимальными идеалами и гомоморфизмами 2-элементной булевой алгебры {истина, ложь} (также известными как 2-значные морфизмы ) следующим образом:

Учитывая гомоморфизм булевой алгебры на {истина, ложь}, прообраз «истины» является ультрафильтром, а обратный образ «ложи» — максимальным идеалом.
Учитывая максимальный идеал булевой алгебры, ее дополнение является ультрафильтром, и существует уникальный гомоморфизм на {истина, ложь}, переводящий максимальный идеал в «ложь».
Учитывая ультрафильтр в булевой алгебре, его дополнение является максимальным идеалом, и существует уникальный гомоморфизм на {истина, ложь}, переводящий ультрафильтр в «истину». ^{[ нужна ссылка ]}

Ультрафильтр на силовой установке комплекта

Учитывая произвольный набор $X,$ его набор мощности ${\mathcal {P}}(X),$ упорядоченная по включению множества , всегда является булевой алгеброй; следовательно, применимы результаты предыдущего раздела. (Ультра)фильтр на ${\mathcal {P}}(X)$ часто называют просто «(ультра)фильтром на $X$ ". ^{[примечание 1]} Учитывая произвольный набор $X,$ ультрафильтр на ${\mathcal {P}}(X)$ это набор ${\mathcal {U}}$ состоящий из подмножеств $X$ такой, что:

Пустое множество не является элементом ${\mathcal {U}}$ .
Если $A$ является элементом ${\mathcal {U}}$ то же самое происходит с каждым суперсетом $B\supset A$ .
Если $A$ и $B$ являются элементами ${\mathcal {U}}$ то же самое и с перекрёстком $A\cap B$ .
Если $A$ является подмножеством $X,$ тогда либо ^{[примечание 4]} $A$ или его дополнение $X\setminus A$ является элементом ${\mathcal {U}}$ .

То же самое, семья ${\mathcal {U}}$ подмножеств $X$ является ультрафильтром тогда и только тогда, когда для любого конечного набора ${\mathcal {F}}$ подмножеств $X$ , есть некоторые $x\in X$ такой, что ${\mathcal {U}}\cap {\mathcal {F}}=F_{x}\cap {\mathcal {F}}$ где $F_{x}=\{Y\subseteq X:x\in Y\}$ является основным ультрафильтром, засеянным $x$ . Другими словами, ультрафильтр можно рассматривать как семейство множеств, которые «локально» напоминают главный ультрафильтр. ^{[ нужна ссылка ]}

Эквивалентная форма данного ${\mathcal {U}}$ — двузначный морфизм , функция $m$ на ${\mathcal {P}}(X)$ определяется как $m(A)=1$ если $A$ является элементом ${\mathcal {U}}$ и $m(A)=0$ в противном случае. Затем $m$ конечно аддитивна и, следовательно, содержание содержит ${\mathcal {P}}(X),$ и каждое свойство элементов $X$ либо истинно почти везде , либо ложно почти везде. Однако, $m$ обычно не является счетно-аддитивной и, следовательно, не определяет меру в обычном смысле.

Для фильтра ${\mathcal {F}}$ это не ультрафильтр, можно определить $m(A)=1$ если $A\in {\mathcal {F}}$ и $m(A)=0$ если $X\setminus A\in {\mathcal {F}},$ уход $m$ неопределенный в другом месте. ^[1]

Приложения

Ультрафильтры на степенных множествах полезны в топологии , особенно в отношении компактных хаусдорфовых пространств, а также в теории моделей при построении ультрапроизведений и ультрастепеней . Каждый ультрафильтр в компактном хаусдорфовом пространстве сходится ровно к одной точке. Точно так же ультрафильтры на булевых алгебрах играют центральную роль в теореме о представлении Стоуна . В теории множеств ультрафильтры используются, чтобы показать, что аксиома конструктивности несовместима с существованием измеримого кардинала $κ$ . Это доказывается путем взятия сверхмощности теоретической вселенной по модулю $κ$ -полного неглавного ультрафильтра. ^[7]

Набор $G$ всех ультрафильтров частичного набора ${\textstyle P}$ может быть топологизирована естественным образом, что фактически тесно связано с упомянутой выше теоремой о представлении. Для любого элемента $x$ из ${\textstyle P}$ , позволять $D_{x}=\left\{U\in G:x\in U\right\}.$ Это наиболее полезно, когда ${\textstyle P}$ снова является булевой алгеброй, так как в этой ситуации множество всех $D_{x}$ является основой компактной топологии Хаусдорфа на $G$ . Особенно, если учесть ультрафильтры на силовом агрегате. ${\mathcal {P}}(S)$ , полученное топологическое пространство представляет собой компактификацию Стоуна – Чеха дискретного пространства мощности $|S|.$

Конструкция ультрапродукта использует в теории моделей ультрафильтры для создания новой модели, начиная с последовательности $X$ -индексированные модели; например, теорему о компактности так можно доказать .В частном случае сверхстепеней возникают элементарные расширения структур. Например, в нестандартном анализе гипердействительные числа могут быть построены как ультрапроизведение действительных чисел , расширяя область обсуждения от действительных чисел до последовательностей действительных чисел. Это пространство последовательностей рассматривается как надмножество действительных чисел путем отождествления каждого вещественного числа с соответствующей постоянной последовательностью. Чтобы распространить знакомые функции и отношения (например, + и <) от вещественных чисел к гиперреальным, естественная идея состоит в том, чтобы определить их поточечно. Но это привело бы к потере важных логических свойств реальности; например, поточечный < не является полным упорядочением. Поэтому вместо этого функции и отношения определяются « поточечно по модулю ». $U$ , где $U$ — ультрафильтр на наборе индексов последовательностей; по теореме Лося это сохраняет все свойства действительных чисел, которые могут быть сформулированы в логике первого порядка . Если $U$ неглавно, то полученное таким образом расширение нетривиально.

В геометрической теории групп неглавные ультрафильтры используются для определения асимптотического конуса группы. Эта конструкция дает строгий способ рассмотреть группу с бесконечности , то есть с крупномасштабной геометрии группы. Асимптотические конусы являются частными примерами ультрапределов метрических пространств .

Онтологическое доказательство существования Бога Гёделя использует в качестве аксиомы то, что набор всех «положительных свойств» является ультрафильтром.

В теории социального выбора неглавные ультрафильтры используются для определения правила (называемого функцией социального благосостояния ) для агрегирования предпочтений бесконечного числа людей. В отличие от теоремы Эрроу о невозможности для конечного числа индивидов такое правило удовлетворяет условиям (свойствам), которые предлагает Эрроу (например, Kirman and Sondermann, 1972). ^[8] Михара (1997, ^[9] 1999) ^[10] Однако показывает, что такие правила представляют практически ограниченный интерес для социологов, поскольку они неалгоритмичны и невычислимы.

См. также

Фильтр (математика) – в математике особое подмножество частично упорядоченного множества.
Фильтр (теория множеств) - семейство множеств, представляющих «большие» множества.
Фильтры в топологии . Использование фильтров для описания и характеристики всех основных топологических понятий и результатов.
Лемма об ультрафильтре : страницы максимально правильного фильтра,
Универсальная сеть – обобщение последовательности точек

Примечания

^ Jump up to: ^а ^б Если $X$ также частично упорядочен, необходимо с особой осторожностью понять из контекста, является ли (ультра)фильтр на ${\mathcal {P}}(X)$ или (ультра)фильтр только на $X$ имеется в виду; оба типа (ультра)фильтров совершенно разные. Некоторые авторы ^{[ нужна ссылка ]} используйте «(ультра)фильтр частично упорядоченного набора» вместо « на произвольном наборе»; т.е. пишут "(ультра)фильтр на $X$ "сокращенно" (ультра)фильтр ${\mathcal {P}}(X)$ ".
^ Чтобы увидеть направление «если»: Если $\left\{x_{1},\ldots ,x_{n}\right\}\in U,$ затем $\left\{x_{1}\right\}\in U,{\text{ or }}\ldots {\text{ or }}\left\{x_{n}\right\}\in U,$ по характеристике №7 из Ультрафильтра (теория множеств)#Характеристики . То есть некоторые $\left\{x_{i}\right\}$ является основным элементом $U.$
^ $U$ неглавен тогда и только тогда, когда он не содержит конечного множества, т. е. (по п. 3 приведенной выше характеризационной теоремы) тогда и только тогда, когда он содержит каждое конечное множество, т. е. каждый член фильтра Фреше.
^ Свойства 1 и 3 подразумевают, что $A$ и $X\setminus A$ не могут оба быть элементами $U.$

Ссылки

^ Jump up to: ^а ^б Алекс Крукман (7 ноября 2012 г.). «Заметки об ультрафильтрах» (PDF) . Семинар по набору математических инструментов Беркли.
^ Jump up to: ^а ^б ^с ^д Дэйви, бакалавр; Пристли, ХА (1990). Введение в решетки и порядок . Кембриджские математические учебники. Издательство Кембриджского университета.
^ Голдбринг, Исаак (2021). «Ультрафильтровальные методы в комбинаторике» . Снимки современной математики из Обервольфаха . Марта Маджиони, София Янс. doi : 10.14760/SNAP-2021-006-EN .
^ «Ультрафильтры и как ими пользоваться» , Бурак Кая, конспект лекций, Математическая деревня Несин, лето 2019.
^ Халбайзен, ЖЖ (2012). Комбинаторная теория множеств . Монографии Спрингера по математике. Спрингер.
^ Беррис, Стэнли Н.; Санкаппанавар, HP (2012). Курс универсальной алгебры (PDF) . ISBN 978-0-9880552-0-9 .
^ Канамори, Высшая бесконечность, с. 49.
^ Кирман, А.; Зондерманн, Д. (1972). «Теорема Эрроу, множество агентов и невидимые диктаторы». Журнал экономической теории . 5 (2): 267–277. дои : 10.1016/0022-0531(72)90106-8 .
^ Михара, HR (1997). «Теорема Эрроу и вычислимость по Тьюрингу» (PDF) . Экономическая теория . 10 (2): 257–276. CiteSeerX 10.1.1.200.520 . дои : 10.1007/s001990050157 . S2CID 15398169 Перепечатано в издании К.В. Велупилаи, С. Замбелли и С. Кинселлы, «Вычислимая экономика», Международная библиотека критических работ по экономике, Эдвард Элгар, 2011. {{cite journal}}: CS1 maint: постскриптум ( ссылка )
^ Михара, HR (1999). «Теорема Эрроу, счетное множество агентов и более видимые невидимые диктаторы» . Журнал математической экономики . 32 (3): 267–277. CiteSeerX 10.1.1.199.1970 . дои : 10.1016/S0304-4068(98)00061-5 .

Библиография

Архангельский Александр Владимирович ; Пономарев, В.И. (1984). Основы общей топологии: задачи и упражнения . Математика и ее приложения. Том. 13. Дордрехт Бостон: Д. Рейдель . ISBN 978-90-277-1355-1 . OCLC 9944489 .
Бурбаки, Николя (1989) [1966]. Общая топология: главы 1–4 [ Общая топология ]. Элементы математики . Берлин, Нью-Йорк: Springer Science & Business Media. ISBN 978-3-540-64241-1 . OCLC 18588129 .
Диксмье, Жак (1984). Общая топология . Тексты для бакалавриата по математике. Перевод Berberian, SK New York: Springer-Verlag . ISBN 978-0-387-90972-1 . ОСЛК 10277303 .
Долецкий, Шимон ; Минард, Фредерик (2016). Основы конвергенции топологии . Нью-Джерси: Всемирная научная издательская компания. ISBN 978-981-4571-52-4 . OCLC 945169917 .
Дугунджи, Джеймс (1966). Топология . Бостон: Аллин и Бэкон. ISBN 978-0-697-06889-7 . OCLC 395340485 .
Часар, Акош (1978). Общая топология . Перевод Часара, Клары. Adam Hilger Ltd. Бристоль, Англия: ISBN 0-85274-275-4 . ОСЛК 4146011 .
Джех, Томас (2006). Теория множеств: издание третьего тысячелетия, переработанное и расширенное . Берлин, Нью-Йорк: Springer Science & Business Media. ISBN 978-3-540-44085-7 . OCLC 50422939 .
Джоши, К.Д. (1983). Введение в общую топологию . Нью-Йорк: ISBN John Wiley and Sons Ltd. 978-0-85226-444-7 . OCLC 9218750 .
Наричи, Лоуренс; Бекенштейн, Эдвард (2011). Топологические векторные пространства . Чистая и прикладная математика (Второе изд.). Бока-Ратон, Флорида: CRC Press. ISBN 978-1584888666 . OCLC 144216834 .
Шехтер, Эрик (1996). Справочник по анализу и его основам . Сан-Диего, Калифорния: Academic Press. ISBN 978-0-12-622760-4 . OCLC 175294365 .
Шуберт, Хорст (1968). Топология . Лондон: ISBN Macdonald & Co. 978-0-356-02077-8 . OCLC 463753 .

Дальнейшее чтение

Комфорт, WW (1977). «Ультрафильтры: некоторые старые и некоторые новые результаты» . Бюллетень Американского математического общества . 83 (4): 417–455. дои : 10.1090/S0002-9904-1977-14316-4 . ISSN 0002-9904 . МР 0454893 .
Комфорт, WW; Негрепонтис, С. (1974), Теория ультрафильтров , Берлин, Нью-Йорк: Springer-Verlag , MR 0396267.
Ультрафильтр в n Lab
«Математическая логика 15, Теорема об ультрафильтре» на YouTube

[notation_warning-1] Jump up to: ^а ^б Если $X$ также частично упорядочен, необходимо с особой осторожностью понять из контекста, является ли (ультра)фильтр на ${\mathcal {P}}(X)$ или (ультра)фильтр только на $X$ имеется в виду; оба типа (ультра)фильтров совершенно разные. Некоторые авторы ^{[ нужна ссылка ]} используйте «(ультра)фильтр частично упорядоченного набора» вместо « на произвольном наборе»; т.е. пишут "(ультра)фильтр на $X$ "сокращенно" (ультра)фильтр ${\mathcal {P}}(X)$ ".

[5] Чтобы увидеть направление «если»: Если $\left\{x_{1},\ldots ,x_{n}\right\}\in U,$ затем $\left\{x_{1}\right\}\in U,{\text{ or }}\ldots {\text{ or }}\left\{x_{n}\right\}\in U,$ по характеристике №7 из Ультрафильтра (теория множеств)#Характеристики . То есть некоторые $\left\{x_{i}\right\}$ является основным элементом $U.$

[6] $U$ неглавен тогда и только тогда, когда он не содержит конечного множества, т. е. (по п. 3 приведенной выше характеризационной теоремы) тогда и только тогда, когда он содержит каждое конечное множество, т. е. каждый член фильтра Фреше.

[exclusive_or-10] Свойства 1 и 3 подразумевают, что $A$ и $X\setminus A$ не могут оба быть элементами $U.$

[Kruckman.2012-2] Jump up to: ^а ^б Алекс Крукман (7 ноября 2012 г.). «Заметки об ультрафильтрах» (PDF) . Семинар по набору математических инструментов Беркли.

[Davey.Priestley.1990-3] Jump up to: ^а ^б ^с ^д Дэйви, бакалавр; Пристли, ХА (1990). Введение в решетки и порядок . Кембриджские математические учебники. Издательство Кембриджского университета.

[4] Голдбринг, Исаак (2021). «Ультрафильтровальные методы в комбинаторике» . Снимки современной математики из Обервольфаха . Марта Маджиони, София Янс. doi : 10.14760/SNAP-2021-006-EN .

[Kaya.2019-7] «Ультрафильтры и как ими пользоваться» , Бурак Кая, конспект лекций, Математическая деревня Несин, лето 2019.

[Halbeisen2012-8] Халбайзен, ЖЖ (2012). Комбинаторная теория множеств . Монографии Спрингера по математике. Спрингер.

[Burris.Sankappanavar.2012-9] Беррис, Стэнли Н.; Санкаппанавар, HP (2012). Курс универсальной алгебры (PDF) . ISBN 978-0-9880552-0-9 .

[11] Канамори, Высшая бесконечность, с. 49.

[12] Кирман, А.; Зондерманн, Д. (1972). «Теорема Эрроу, множество агентов и невидимые диктаторы». Журнал экономической теории . 5 (2): 267–277. дои : 10.1016/0022-0531(72)90106-8 .

[mihara97-13] Михара, HR (1997). «Теорема Эрроу и вычислимость по Тьюрингу» (PDF) . Экономическая теория . 10 (2): 257–276. CiteSeerX 10.1.1.200.520 . дои : 10.1007/s001990050157 . S2CID 15398169 Перепечатано в издании К.В. Велупилаи, С. Замбелли и С. Кинселлы, «Вычислимая экономика», Международная библиотека критических работ по экономике, Эдвард Элгар, 2011. {{cite journal}}: CS1 maint: постскриптум ( ссылка )

[mihara99-14] Михара, HR (1999). «Теорема Эрроу, счетное множество агентов и более видимые невидимые диктаторы» . Журнал математической экономики . 32 (3): 267–277. CiteSeerX 10.1.1.199.1970 . дои : 10.1016/S0304-4068(98)00061-5 .

[примечание 1]

[1]

[2]

[3]

[примечание 2]

[примечание 3]

[4]

[5]

[6]

[примечание 4]

[7]

[8]

[9]

[10]