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

Максимально правильный фильтр

Диаграмма Хассе делителей числа 210, упорядоченных по соотношению делитель числа , с верхним набором ↑14 , окрашенным в темно-зеленый цвет. Это основной фильтр , но не ультрафильтр , поскольку его можно расширить до более крупного нетривиального фильтра ↑2, включив также светло-зеленые элементы. Поскольку ↑2 нельзя продолжать дальше, это ультрафильтр.

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

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

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

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

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

Формально, if — множество, частично упорядоченное к тому времени ${\textstyle P}$ ${\displaystyle \,\leq \,}$

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

.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}Виды и существование ультрафильтров

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

Примечания

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

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

1. Алекс Крукман (7 ноября 2012 г.). «Заметки об ультрафильтрах» (PDF) . Семинар по набору математических инструментов Беркли.
2. Дэйви, бакалавр; Пристли, ХА (1990). Введение в решетки и порядок . Кембриджские математические учебники. Издательство Кембриджского университета.
3. Голдбринг, Исаак (2021). Марта Маджиони, София Янс. «Ультрафильтровальные методы в комбинаторике». Снимки современной математики из Обервольфаха . doi : 10.14760/SNAP-2021-006-RU.
4. «Ультрафильтры и как их использовать», Бурак Кая, конспект лекций, Математическая деревня Несин, лето 2019.
5. Халбайзен, ЖЖ (2012). Комбинаторная теория множеств . Монографии Спрингера по математике. Спрингер.
6. Беррис, Стэнли Н.; Санкаппанавар, HP (2012). Курс универсальной алгебры (PDF) . ISBN 978-0-9880552-0-9.
7. Канамори, Высшая бесконечность, с. 49.
8. Кирман, А.; Зондерманн, Д. (1972). «Теорема Эрроу, множество агентов и невидимые диктаторы». Журнал экономической теории . 5 (2): 267–277. дои : 10.1016/0022-0531(72)90106-8.
9. Михара, HR (1997). «Теорема Эрроу и вычислимость по Тьюрингу» (PDF) . Экономическая теория . 10 (2): 257–276. CiteSeerX 10.1.1.200.520 . дои : 10.1007/s001990050157. S2CID  15398169Перепечатано в издании К.В. Велупилаи, С. Замбелли и С. Кинселлы, «Вычислимая экономика», Международная библиотека критических работ по экономике, Эдвард Элгар, 2011. {{cite journal}}: CS1 maint: постскриптум ( ссылка )
10. Михара, 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. ОКЛК  9944489.
• Бурбаки, Николя (1989) [1966]. Общая топология: главы 1–4 [ Общая топология ]. Элементы математики . Берлин, Нью-Йорк: Springer Science & Business Media. ISBN 978-3-540-64241-1. ОСЛК  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. ОСЛК  395340485.
• Часар, Акош (1978). Общая топология . Перевод Часара, Клары. Бристоль, Англия: ISBN Adam Hilger Ltd. 0-85274-275-4. ОСЛК  4146011.
• Джех, Томас (2006). Теория множеств: издание третьего тысячелетия, переработанное и расширенное . Берлин, Нью-Йорк: Springer Science & Business Media. ISBN 978-3-540-44085-7. ОСЛК  50422939.
• Джоши, К.Д. (1983). Введение в общую топологию . Нью-Йорк: ISBN John Wiley and Sons Ltd. 978-0-85226-444-7. ОСЛК  9218750.
• Наричи, Лоуренс; Бекенштейн, Эдвард (2011). Топологические векторные пространства . Чистая и прикладная математика (Второе изд.). Бока-Ратон, Флорида: CRC Press. ISBN 978-1584888666. OCLC  144216834.
• Шехтер, Эрик (1996). Справочник по анализу и его основам . Сан-Диего, Калифорния: Academic Press. ISBN 978-0-12-622760-4. ОСЛК  175294365.
• Шуберт, Хорст (1968). Топология . Лондон: ISBN Macdonald & Co. 978-0-356-02077-8. ОСЛК  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