Квантор фильтра

В математике фильтр на множестве $X$ неформально дает представление о том, какие подмножества $A\subseteq X$ являются «большими». Кванторы фильтра — это тип логических кванторов, которые, неформально, говорят, верно ли утверждение для «большинства» элементов $X.$ Такие кванторы часто используются в комбинаторике , теории моделей (например, при работе с ультрапроизведениями ) и в других областях математической логики , где используются (ультра)фильтры.

Фон

Здесь мы будем использовать соглашение теории множеств, где фильтр ${\mathcal {F}}$ на съемочной площадке $X$ определяется как теоретико-порядковый собственный фильтр в частично упорядоченном множестве $({\mathcal {P}}(X),\subseteq ),$ то есть подмножество ${\mathcal {P}}(X)$ такой, что:

$\varnothing \notin {\mathcal {F}}$ и $X\in {\mathcal {F}}$ ;
Для всех $A,B\in {\mathcal {F}},$ у нас есть $A\cap B\in {\mathcal {F}}$ ;
Для всех $A\subseteq B\subseteq X,$ если $A\in {\mathcal {F}}$ затем $B\in {\mathcal {F}}.$

Вызов фильтра ${\mathcal {F}}$ на $X$ является ультрафильтром , если для каждого $A\subseteq X,$ или $A\in {\mathcal {F}}$ или $X\setminus A\in {\mathcal {F}}.$

Учитывая фильтр ${\mathcal {F}}$ на съемочной площадке $X,$ мы говорим подмножество $A\subseteq X$ является ${\mathcal {F}}$ -стационарно , если для всех $B\in {\mathcal {F}},$ у нас есть $A\cap B\neq \varnothing .$ ^[1]

Определение

Позволять ${\mathcal {F}}$ быть фильтром на съемочной площадке $X.$ Определим кванторы фильтра $\forall _{\mathcal {F}}x$ и $\exists _{\mathcal {F}}x$ как формальные логические символы со следующей интерпретацией:

\forall _{\mathcal {F}}x\ \varphi (x)\iff \{x\in X:\varphi (x)\}\in {\mathcal {F}}

\exists _{\mathcal {F}}x\ \varphi (x)\iff \{x\in X:\varphi (x)\}

является

{\mathcal {F}}

-стационарный

для каждой первого порядка формулы $\varphi (x)$ с одной свободной переменной. Они также допускают альтернативные определения как

\forall _{\mathcal {F}}x\ \varphi (x)\iff \exists A\in {\mathcal {F}}\ \ \forall x\in A\ \ \varphi (x)

\exists _{\mathcal {F}}x\ \varphi (x)\iff \forall A\in {\mathcal {F}}\ \ \exists x\in A\ \ \varphi (x)

Когда ${\mathcal {F}}$ является ультрафильтром, два определенных выше квантора совпадают, и мы часто будем использовать обозначение ${\mathcal {F}}x$ вместо. Устно мы можем произнести ${\mathcal {F}}x$ как «для ${\mathcal {F}}$ -почти все $x$ ", "для ${\mathcal {F}}$ -большинство $x$ ", "для большинства $x$ (в соответствии с ${\mathcal {F}}$ )», или «для большинства $x$ (в соответствии с ${\mathcal {F}}$ )». В тех случаях, когда фильтр понятен, мы могли бы опустить упоминание о ${\mathcal {F}}.$

Характеристики

Кванторы фильтра $\forall _{\mathcal {F}}x$ и $\exists _{\mathcal {F}}x$ удовлетворяют следующим логическим тождествам, ^[1] для всех формул $\varphi ,\psi$ :

Двойственность: $\forall _{\mathcal {F}}x\ \varphi (x)\iff \neg \exists _{\mathcal {F}}x\ \neg \varphi (x)$
Ослабление: $\forall x\ \varphi (x)\implies \forall _{\mathcal {F}}x\ \varphi (x)\implies \exists _{\mathcal {F}}x\ \varphi (x)\implies \exists x\ \varphi (x)$
Соединение:
- $\forall _{\mathcal {F}}x\ {\big (}\varphi (x)\land \psi (x){\big )}\iff {\big (}\forall _{\mathcal {F}}x\ \varphi (x){\big )}\land {\big (}\forall _{\mathcal {F}}x\ \psi (x){\big )}$
- $\exists _{\mathcal {F}}x\ {\big (}\varphi (x)\land \psi (x){\big )}\implies {\big (}\exists _{\mathcal {F}}x\ \varphi (x){\big )}\land {\big (}\exists _{\mathcal {F}}x\ \psi (x){\big )}$
Дизъюнкция:
- $\forall _{\mathcal {F}}x\ {\big (}\varphi (x)\lor \psi (x){\big )}\;\Longleftarrow \;{\big (}\forall _{\mathcal {F}}x\ \varphi (x){\big )}\lor {\big (}\forall _{\mathcal {F}}x\ \psi (x){\big )}$
- $\exists _{\mathcal {F}}x\ {\big (}\varphi (x)\lor \psi (x){\big )}\;\Longleftrightarrow \;{\big (}\exists _{\mathcal {F}}x\ \varphi (x){\big )}\lor {\big (}\exists _{\mathcal {F}}x\ \psi (x){\big )}$
Если ${\mathcal {F}}\subseteq {\mathcal {G}}$ ${\mathcal {F}}\subseteq {\mathcal {G}}$ включены ли фильтры $X,$ $X,$ затем:
- $\forall _{\mathcal {F}}x\ \varphi (x)\implies \forall _{\mathcal {G}}x\ \varphi (x)$
- $\exists _{\mathcal {F}}x\ \varphi (x)\;\Longleftarrow \;\exists _{\mathcal {G}}x\ \varphi (x)$

Кроме того, если ${\mathcal {F}}$ является ультрафильтром, два квантора фильтра совпадают: $\forall _{\mathcal {F}}x\ \varphi (x)\iff \exists _{\mathcal {F}}x\ \varphi (x).$ ^{[ нужна ссылка ]} Переименование этого квантификатора ${\mathcal {F}}x,$ имеют место следующие свойства:

Отрицание: ${\mathcal {F}}x\ \varphi (x)\iff \neg {\mathcal {F}}x\ \neg \varphi (x)$
Ослабление: $\forall x\ \varphi (x)\implies {\mathcal {F}}x\ \varphi (x)\implies \exists x\ \varphi (x)$
Соединение: ${\mathcal {F}}x\ {\big (}\varphi (x)\land \psi (x){\big )}\iff {\big (}{\mathcal {F}}x\ \varphi (x){\big )}\land {\big (}{\mathcal {F}}x\ \psi (x){\big )}$
Дизъюнкция: ${\mathcal {F}}x\ {\big (}\varphi (x)\lor \psi (x){\big )}\iff {\big (}{\mathcal {F}}x\ \varphi (x){\big )}\lor {\big (}{\mathcal {F}}x\ \psi (x){\big )}$

В общем, кванторы фильтров не коммутируют ни друг с другом, ни с обычными $\forall$ и $\exists$ квантификаторы. ^{[ нужна ссылка ]}

Примеры

Если ${\mathcal {F}}=\{X\}$ это тривиальный фильтр на $X,$ затем распаковав определение, мы имеем $\forall _{\mathcal {F}}x\ \varphi (x)\iff \{x\in X:\varphi (x)\}=X,$ и $\exists _{\mathcal {F}}x\ \varphi (x)\iff \{x\in X:\varphi (x)\}\cap X\neq \varnothing .$ Это восстанавливает обычное $\forall$ и $\exists$ квантификаторы.
Позволять ${\mathcal {F}}^{\infty }$ быть фильтром Фреше на бесконечном множестве $X,$ Затем, $\forall _{{\mathcal {F}}^{\infty }}x\ \varphi (x)$ имеет место тогда и только тогда, когда $\varphi (x)$ имеет место для коконечного многих $x\in X,$ и $\exists _{{\mathcal {F}}^{\infty }}x\ \varphi (x)$ имеет место тогда и только тогда, когда $\varphi (x)$ имеет место для бесконечно многих $x\in X.$ Кванторы $\forall _{{\mathcal {F}}^{\infty }}$ и $\exists _{{\mathcal {F}}^{\infty }}$ чаще обозначаются $\forall ^{\infty }$ и $\exists ^{\infty },$ соответственно.
Позволять ${\mathcal {M}}$ быть «фильтром измерения» на $[0,1],$ генерируется всеми подмножествами $A\subseteq [0,1]$ с мерой Лебега $\mu (A)=1.$ Приведенная выше конструкция дает нам «квантификаторы меры»: $\forall _{\mathcal {M}}x\ \varphi (x)$ имеет место тогда и только тогда, когда $\varphi (x)$ держится почти везде , и $\exists _{\mathcal {M}}x\ \varphi (x)$ имеет место тогда и только тогда, когда $\varphi (x)$ выполняется на множестве положительной меры. ^[2]
Предполагать ${\mathcal {F}}_{A}$ ${\mathcal {F}}_{A}$ является основным фильтром на некотором множестве $A\subseteq X.$ $A\subseteq X.$ Тогда у нас есть $\forall _{{\mathcal {F}}_{A}}x\ \varphi (x)\iff \forall x\in A\ \varphi (x),$ $\forall _ {{\mathcal {F}}_{A}}x\ \varphi (x)\iff \forall x\in A\ \varphi (x),$ и $\exists _{{\mathcal {F}}_{A}}x\ \varphi (x)\iff \exists x\in A\ \varphi (x).$ $\exists _ {{\mathcal {F}}_{A}}x\ \varphi (x)\iff \exists x\in A\ \varphi (x).$
- Если ${\mathcal {U}}_{d}$ является основным ультрафильтром элемента $d\in X,$ тогда у нас есть ${\mathcal {U}}_{d}\,x\ \varphi (x)\iff \varphi (d).$

Использовать

Полезность кванторов фильтров заключается в том, что они часто дают более краткий и ясный способ выразить определенные математические идеи. Например, возьмем определение сходимости вещественнозначной последовательности : последовательность $(a_{n})_{n\in \mathbb {N} }\subseteq \mathbb {R}$ сходится к точке $a\in \mathbb {R}$ если

\forall \varepsilon >0\ \ \exists N\in \mathbb {N} \ \ \forall n\in \mathbb {N} \ {\big (}\ n\geq N\implies \vert a_{n}-a\vert <\varepsilon \ {\big )}

Использование квантора Фреше $\forall ^{\infty }$ как определено выше, мы можем дать более хорошее (эквивалентное) определение:

\forall \varepsilon >0\ \ \forall ^{\infty }n\in \mathbb {N} :\ \vert a_{n}-a\vert <\varepsilon

Кванторы фильтров особенно полезны в конструкциях, включающих фильтры. В качестве примера предположим, что $X$ имеет бинарную операцию $+$ определено на нем. Существует естественный способ расширить ^[3] $+$ к $\beta X,$ набор ультрафильтров на $X$ : ^[4]

{\mathcal {U}}\oplus {\mathcal {V}}={\big \{}A\subseteq X:\ {\mathcal {U}}x\ {\mathcal {V}}y\ \ x+y\in A{\big \}}

При понимании квантора ультрафильтра это определение становится достаточно интуитивным. Там говорится, что ${\mathcal {U}}\oplus {\mathcal {V}}$ это совокупность подмножеств $A\subseteq X$ такой, что для большинства $x$ (в соответствии с ${\mathcal {U}}$ ) и для большинства $y$ (в соответствии с ${\mathcal {V}}$ ), сумма $x+y$ находится в $A.$ Сравните это с эквивалентным определением без кванторов ультрафильтра:

{\mathcal {U}}\oplus {\mathcal {V}}={\big \{}A\subseteq X:\ \{x\in X:\ \{y\in X:\ x+y\in A\}\in {\mathcal {V}}\}\in {\mathcal {U}}{\big \}}

Смысл этого гораздо менее ясен.

Эта повышенная интуиция также очевидна в доказательствах с использованием ультрафильтров. Например, если $+$ ассоциативен по $X,$ используя первое определение $\oplus ,$ из этого тривиально следует, что $\oplus$ ассоциативен по $\beta X.$ Доказательство этого с использованием второго определения требует гораздо большей работы. ^[5]

См. также

Фильтр (математика) – в математике особое подмножество частично упорядоченного множества.
Фильтр (теория множеств) - семейство множеств, представляющих «большие» множества.
Обобщенный квантор - выражение, обозначающее набор множеств в формальной семантике.
Компактификация Стоуна-Чеха - универсальное отображение топологического пространства X в компактное хаусдорфово пространство βX, такое, что любое отображение X в компактное хаусдорфово пространство факторизуется через βX однозначно; если X — Тихонов, то X — плотное подпространство
Ультрафильтр – Максимально правильный фильтр
Ультрафильтр (теория множеств) — страницы максимально правильного фильтра,

Ссылки

^ Перейти обратно: ^а ^б Муммерт, Карл (30 ноября 2014 г.). «Кванторы фильтра» (PDF) . Университет Маршалла .
^ «логика — ссылки на кванторы фильтров» . Математический обмен стеками . Проверено 27 февраля 2020 г.
^ Это расширение $+$ в том смысле, что мы можем рассматривать $X$ как подмножество $\beta X$ путем сопоставления каждого $x\in X$ к главному ультрафильтру ${\mathcal {U}}_{x}$ на $x.$ Тогда у нас есть ${\mathcal {U}}_{x}\oplus {\mathcal {U}}_{y}={\mathcal {U}}_{(x+y)}.$
^ «Как пользоваться ультрафильтрами | Tricki» . www.tricki.org . Проверено 26 февраля 2020 г.
^ Тодорцевич, Стево (2010). Введение в пространства Рамсея . Издательство Принстонского университета. п. 32. ISBN 978-0-691-14541-9 . OCLC 839032558 .

[:0-1] Перейти обратно: ^а ^б Муммерт, Карл (30 ноября 2014 г.). «Кванторы фильтра» (PDF) . Университет Маршалла .

[2] «логика — ссылки на кванторы фильтров» . Математический обмен стеками . Проверено 27 февраля 2020 г.

[3] Это расширение $+$ в том смысле, что мы можем рассматривать $X$ как подмножество $\beta X$ путем сопоставления каждого $x\in X$ к главному ультрафильтру ${\mathcal {U}}_{x}$ на $x.$ Тогда у нас есть ${\mathcal {U}}_{x}\oplus {\mathcal {U}}_{y}={\mathcal {U}}_{(x+y)}.$

[4] «Как пользоваться ультрафильтрами | Tricki» . www.tricki.org . Проверено 26 февраля 2020 г.

[5] Тодорцевич, Стево (2010). Введение в пространства Рамсея . Издательство Принстонского университета. п. 32. ISBN 978-0-691-14541-9 . OCLC 839032558 .

[1]

[2]

[3]

[4]

[5]