Фильтры и ультрафильтры

[Профессор Снэйп]

Не ахти какая олимпиадная задача, но всё же...

Пусть $\mathcal{F}_1, \ldots, \mathcal{F}_k$ --- различные ультрафильтры на $I$, $\mathcal{H}$ --- фильтр на $I$ и $\mathcal{H} \supseteq \mathcal{F}_1 \cap \ldots \cap \mathcal{F}_k$. Доказать, что существует ровно $2^k-1$ возможностей для $\mathcal{H}$.

На всякий случай напомню необходимые определения. Пусть $I$ --- произвольное непустое множество, а $\mathcal{D}$ --- семейство подмножеств $I$. Тогда $\mathcal{D}$ называется фильтром на $I$, если выполнены следующие аксиомы.

1) $\varnothing \not\in \mathcal{D}$, $I \in \mathcal{D}$;
2) если $X \in \mathcal{D}$ и $X \subseteq Y \subseteq I$, то $Y \in \mathcal{D}$;
3) если $X,Y \in \mathcal{D}$, то $X \cap Y \in \mathcal{D}$.

Фильтр $\mathcal{D}$ называется ультрафильтром, если для него в дополнение к перечисленным трём выполняется ещё одна аксиома:

4) для любого $X \subseteq I$ либо $X \in \mathcal{D}$, либо $I \setminus X \in \mathcal{D}$.

[AGu]

Веселая задачка, спасибо.

Если пульнуть стоуновской пушкой, то эти воробьи разлетятся примерно так...

Пусть $Q:=\beta I$ --- стоуновский компакт булевой алгебры $\mathcal P(I)$.
Тогда ультрафильтры --- это точки в $Q$,
фильтры --- непустые замкнутые подмножества $Q$,
а задача звучит следующим образом.
Пусть $q_1,\dots,q_k$ --- различные точки в $Q$,
$F$ --- непустое замкнутое подмножество $Q$ и $F\subseteq\{q_1,\dots,q_k\}$.
Доказать , что существует ровно $2^k-1$ возмозжностей для $F$.

[Профессор Снэйп]

AGu в сообщении #221763 писал(а):

Если пульнуть стоуновской пушкой...

А если при помощи палки и верёвки?

[Руст]

Предположим, что Н не содержится ни в одном из этих ультрафильтров. Тогда существуют подмножества фильтра H, что $\forall i \ X_i\not \in F_i$. Соответственно их пересечение X не принадлежит ни одному из ультрафильтров, поэтому по условию X и его дополнение принадлежит H - противоречие. Всего имеется $2^k-1$ подмножеств фильтров. H должен содержать содержать один из вариантов непустого пересечения этих ультрафильтров. Все они разные и составляют те самые $2^k-1$ вариантов для H.

[Профессор Снэйп]

Руст в сообщении #221886 писал(а):

Всего имеется $2^k-1$ подмножеств фильтров. H должен содержать содержать один из вариантов непустого пересечения этих ультрафильтров. Все они разные и составляют те самые $2^k-1$ вариантов для H.

Вот этого я не понял.

[Руст]

Пусть $S=\{i_1,..,i_m\}$ некоторое непустое подмножество множества ультрафильтров. Обозначим
$H_S= \mathcal{F}_{i_1} \cap \ldots \cap \mathcal{F}_{i_m}$ пересечение этих фильтров. Всего $2^k-1$ вариантов $S$ и $H_S$.
Если $i\not \in S$, то $H_S$ не содержится в $\mathcal{F}_i$. Действительно, так как фильтры разные существует множество $X_{i,i_j}\in \mathcal{F}_i$ принадлежащей рассматриваемому фильтру и не принадлежащей одному из фильтров из S. Взяв их пересечение, получим непустое множество X, содержащее в рассматриваемом фильтре и не содержащееся ни в одном из ультрафильтровмножества S. Дополнение к множеству X содержится в $H_S$ но не содержится в $\mathcal{F}_i$. Это и оказывает, что все $H_s$ разные.

[Профессор Снэйп]

А почему наше $\mathcal{H}$ обязано совпадать с одним из $\mathcal{H}_S$?

[Руст]

Как уже показано, $H$ содержится в некотором $H_S$ и по условию содержит самое маленькое. Для любого ультрафильтра F из того, что H содержится в пересечении $H_s$ и $F$ получается противоречие прежним способом.
Вообще для фильтров можно ввести их точки, как множество ультрафильтров, которым он принадлежит. Филтры имеющие конечное множество точек определяются однозначно как пересечения своих точек.

[Профессор Снэйп]

Руст в сообщении #222105 писал(а):

Как уже показано, $H$ содержится в некотором $H_S$ и по условию содержит самое маленькое. Для любого ультрафильтра F из того, что H содержится в пересечении $H_s$ и $F$ получается противоречие прежним способом.

Опять не понял. Каким ещё "прежним способом"?

Давайте так. Предположим, что $\mathcal{F}_1 \supset \mathcal{H} \supset \mathcal{F}_1 \cap \mathcal{F}_2$ (включения строгие). Покажите подробно, где тут противоречие.

[mihiv]

Пусть $I$ конечное множество, тогда из аксиом $ 1,2,3 $ следует, что фильтры и ультрафильтры устроены следующим образом: они содержат некоторое подмножество множества $S$ (минимальное подмножество) и подмножества вида $S \cup A_i$ где $A_i$- всевозможные подмножества множества $I$, такие, что $S \cap A_i= \varnothing$. Таким образом каждый фильтр (ультрафильтр) полностью определяется заданием его минимального подмножества $S$.
Используя аксиому $4$, получим, что для ультрафильтра его минимальное подмножество состоит лишь из одного элемента. Пусть $s_i$ - элементы, образующие минимальные подмножества ультрафильтров $ \mathcal {F}_i $. Тогда $ \mathcal{F}_1 \cap , \dots \cap \mathcal{F}_k$ содержит подмножество $\{ s_1, \dots s_k \}$ , а также семейство подмножеств $ \{ s_1, \dots s_k,A_i \}$, где $A_i$ - всевозможные подмножества $I$, не содержащие элементов $s_1, \dots s_k$.
Будем теперь строить фильтры, задавая их с помощью минимальных подмножеств: $\{ s_i \}; \{ s_i,s_j \}; \{ s_i, s_j,s_l \}; \dots \{s_1, \dots s_k \}$. Всего получим $2^k-1$ фильтров. Очевидно, что $ \mathcal {F}_1 \cap \dots \mathcal {F}_k$ содержится в каждом из этих фильтров.

[Профессор Снэйп]

mihiv в сообщении #226145 писал(а):

Пусть $I$ конечное множество...

Конечное множество рассматривать не интересно. На конечном $I$ все фильтры --- главные. Случай, можно сказать, вырожденный и донельзя тривиальный.

Задача представляет интерес как раз для бесконечного $I$.

[Инт]

Профессор Снэйп в сообщении #221707 писал(а):

Пусть $\mathcal{F}_1, \ldots, \mathcal{F}_k$ --- различные ультрафильтры на $I$, $\mathcal{H}$ --- фильтр на $I$ и $\mathcal{H} \supseteq \mathcal{F}_1 \cap \ldots \cap \mathcal{F}_k$. Доказать, что существует ровно $2^k-1$ возможностей для $\mathcal{H}$.

Профессор Снэйп, уточните условия задачи. Поясните, что означает фраза "Доказать, что существует ровно $2^k-1$ возможностей для $\mathcal{H}$". Что это за возможности? Число фильтров? Пусть $\mathcal{F}_1, \ldots, \mathcal{F}_{k+1}$ --- различные ультрафильтры на $I$, $\mathcal{H}$ --- фильтр на $I$ и $\mathcal{H} \supseteq \mathcal{F}_1 \cap \ldots \cap \mathcal{F}_k$. Тогда, тем более $\mathcal{H} \supseteq \mathcal{F}_1 \cap \ldots \cap \mathcal{F}_{k+1}$. Тогда, что существует ровно $2^{k+1}-1$ каких-то непонятных возможностей для $\mathcal{H}$?

[mihiv]

Пусть $I$ произвольное множество, $S_i= \bigcap \limits _{ \alpha} A_{ \alpha}^i \not= \varnothing$, где $A_{\alpha}^i$-подмножества, образующие ультрафильтр $\mathcal {F}_i, i=1, \dots, k$. Тогда доказательство такое же, как для конечного множества $I$. Применяем к каждому ультрафильтру аксиому 4, и получаем, что каждое $S_i$ содержит лишь один элемент $s_i$, образуем набор фильтров с помощью минимальных подмножеств $\{s_i\}, \{s_i, s_j\}, \dots, \{s_1, \dots,s_k\}$. Всего получим $2^k-1$ фильтров, все они различны и содержат $ \mathcal {F}_1 \cap \dots \cap \mathcal {F}_k$. Остался недоказанным случай, когда одно или несколько $S_i = \varnothing$.

[Профессор Снэйп]

mihiv в сообщении #227101 писал(а):

Пусть $I$ произвольное множество, $S_i= \bigcap \limits _{ \alpha} A_{ \alpha}^i \not= \varnothing$, где $A_{\alpha}^i$-подмножества, образующие ультрафильтр $\mathcal {F}_i, i=1, \dots, k$. Тогда доказательство такое же, как для конечного множества $I$. Применяем к каждому ультрафильтру аксиому 4, и получаем, что каждое $S_i$ содержит лишь один элемент $s_i$, образуем набор фильтров с помощью минимальных подмножеств $\{s_i\}, \{s_i, s_j\}, \dots, \{s_1, \dots,s_k\}$. Всего получим $2^k-1$ фильтров, все они различны и содержат $ \mathcal {F}_1 \cap \dots \cap \mathcal {F}_k$. Остался недоказанным случай, когда одно или несколько $S_i = \varnothing$.

Другими словами, Вы разобрали случай, когда все ультрафильтры --- главные. Он лёгок и по сути ничем не отличается от конечного случая. Но, конечно же, ультрафильтры могут быть и не главными

-- Вт июл 07, 2009 16:38:12 --

mihiv, попробуйте лучше рассмотреть случай $k=2$ и ультрафильтры --- произвольные.