Filters and Ideals

#SetTheory

Let $S$ be a nonempty set. A filter on $S$ is a collection $F$ of subsets of $S$ that satisfies the following conditions:

$S \in F$ , $\emptyset \notin F$
If $X, Y \in F$ then $X \cap Y \in F$
If $X \in F$ , and $X \subseteq Y \subseteq S$ , then $Y \in F$

A trivial example of a filter on $S$ is the collection $F = {S}$ that consists only of the set $S$ itself. This trivial filter on $S$ is the smallest filter on $S$ ; it is included in every filter on $S$ .

Let $A$ be a nonempty subset of $S$ , and let us consider the collection $$
F = {X \subseteq S\mid A \subseteq X }

T h e c o l l e c t i o n $ F $ i s c a l l e d t h e * p r i n c i p a l f i l t e r * o n $ S $ * g e n e r a t e d * b y $ A $ . I f w e s e t $ A = {a} $, w h e r e $ a \in S $, t h e p r i n c i p a l f i l t e r $ $ F = {X \subseteq S ∣ a \in X} $ $ i s * m a x i m a l * : t h e r e i s n o f i l t e r $ F^{'} $ o n $ S $ s u c h t h a t $ F \subset F^{'} $ . W e g e t t h a t i f $ A $ h a s a t l e a s t $ 2 $ e l e m e n t s, t h e n t h e p r i n c i p a l f i l t e r o f $ A $ i s n o t m a x i m a l * * D e f * * : L e t $ P $ b e a n o n e m p t y f a m i l y o f s u b s e t s o f $ S $, t h e n t h e * k e r n e l o f * $ P $ i s t h e i n t e r s e c t i o n o f a l l s e t s i n $ P $ : $ $ \ker P := ⋂ P = ⋂_{B \in P} B

a nonempty family of sets $P$ is called:

free if $\ker P = \emptyset$ , and fixed if $\ker P \neq \emptyset$
principal if $\ker P \in P$
principal at a point if $\ker P \in P$ and $\ker P$ is a singleton set, $\ker P = {x}$ then $P$ is said to be principal at $x$ .

We see that any principal filter is not free.

Let $S$ be infinite, and let $F = {X \subseteq S ∣ | S ∖ X | < ℵ_{0}}$ . $F$ is the filter of all cofinite subsets of $S$ . This is special and called a Fréchet filter

A filter is free iff it contains the Fréchet filter

Ideals

Def: Let $S$ be a nonempty set. An ideal of $S$ is a collection $I$ of subsets of $S$ that satisfies the following properties:

$\emptyset \in I$ , and $S \notin I$
If $X, Y \in I$ , then $X \cup Y \in S$
if $Y \in I$ , and $X \subseteq Y$ , then $X \in S$

The trivial ideal on $S$ is ${\emptyset}$ . A principal ideal is an ideal of the form $$I = {X \mid X \subseteq A} = \mathcal P(A)$$ where $A \subseteq S$ .

A family of sets $I$ of $X$ , is an ideal iff $I$ is hereditary and $I$ is a ring

To see how filters and ideals are related, note that if $F$ is a filter on $S$ , then $$ I = {S\setminus X \mid X \in F}$$is an ideal, and vice versa, if $I$ is an ideal, then $$F = {S\setminus X \mid X\in I}$$is a filter. Two objects related by the equations above are called dual to each other.

Filter Base or Prefilters

Def: Given a filter $F$ on the set $X$ , a nonempty sub collection $B$ of $F$ is a filter base or prefilter for $F$ if it satisfies that for every $A \in F$ , there's a $C \in B$ , such that $C \subseteq A$ .

Prop: Let $X$ be a set and $B$ be a nonempty family of $X$ . Then $B$ is filter base on $X$ iff $\emptyset \notin B$ , for any $A_{1}, A_{2} \in B$ , there exists a $A_{3} \in B$ such that $A_{3} \subseteq A_{1} \cap A_{2}$ .

If $B$ is a nonempty family of subsets of $X$ , such that satisfies the condition:

(⋆) \emptyset \notin B \land \forall A_{1}, A_{2} \in B \exists A_{3} \in B [A_{3} \subseteq A_{1} \cap A_{2}]

then the filter that contains $B$ as a filter base is the collection $$F_B = {F \subseteq X \mid \exists A \in B [A \subseteq F]}$$ The filter $F_{B}$ is the filter generated by the filter base $B$ .

Def: Let $F_{1}$ and $F_{2}$ be prefilters on $X$ , then we can add a preorder them: we say that $F_{2}$ refines $F_{1}$ and write $F_{1} \leq F_{2}$ if for the corresponding filters $F_{1} \subseteq F_{2}$ . It is not hard that this holds iff for every $A_{1} \in F_{1}$ there exists $A_{2} \in F_{2}$ such that $A_{2} \subseteq A_{1}$ . If $F_{1} \leq F_{2} \leq F_{1}$ We say that $F_{1}$ and $F_{2}$ are equivalent prefilters and write $F_{1} \sim F_{2}$ .

Def: A system of sets $S$ has the finite intersection property if every nonempty finite subsystem of $S$ has nonempty intersection. Sometimes systems with this property are called centred.

Any filter and any filter base have the finite intersection property.

Prop: Let $f : X \to Y$ and $F$ be a filter on $X$ . Then $f [F]$ is the image of the filter $F$ under $f$ , is a prefilter of $Y$ . Similarlty, if $G$ is a filter on $Y$ , then $f^{- 1} [G]$ is a prefilter of $X$ .

If we have a nonempty system $S$ with the finite intersection property, then $\emptyset \notin π (S)$ , the $π$ -system generated by $S$ , is a filter base, and we can generate a filter $F_{π (S)}$ .

Lemma: Let $G$ be a nonempty collection of subsets of $S$ and let $G$ have the finite intersection property. Then there's is a filter $F$ on $S$ , such that $G \subseteq F$ . The proof is the argument above, and it is the smallest filter that contains $G$ .

Prop: Let $I$ be a family of subsets of $X$ , the following are equivalent:

$I$ has the finite intersection property
there exists a prefilter $F$ , such that $I \subseteq F$
there exists a filter $F$ such that $I \subseteq F$

This is why, in the context of filters, sets with the finite intersection property are called filter subbase.

Def: A family of prefilters ${F_{i}}_{i \in I}$ on a set $X$ is compatible if there exists a prefilter $F \supseteq ⋃_{i \in I} F_{i}$ , i.e., $⋃_{i \in I} F_{i}$ is a filter subbase. This occurs iff every finite subset $J \subseteq I$ and any assignment $j \mapsto A_{j} \in F_{j}$ we have that $⋂_{j \in J} A_{j} \neq \emptyset$ .

Ultrafilters

Def: A filter $U$ on $S$ is an ultrafilter if for every $X \subseteq S$ , either $X \in U$ or $S ∖ X \in U$ .

Def: An ideal $I$ on $S$ is a prime ideal if for every $X \subseteq S$ , either $X \in I$ or $S ∖ X \in I$

Lemma: A filter $F$ on $S$ is an ultrafilter iff $F$ is a maximal filter.

Th: Let $X$ be a set. The following are equivalent:

$F$ is an ultrafilter on $X$
$F$ is a maximal centered family
$F$ is a filter base with the property: for all $A \subseteq X$ , if $A \cap B \neq \emptyset$ for all $B \in F$ , then $A \in F$
$F$ is a maximal filter
$F$ is a centered family with the property: for all $A \subseteq X$ , either $A \in F$ or $X ∖ A \in F$

Th: Every filter $F$ on $S$ , can be extended to an ultrafilter on $S$ .

Cor: Every centered family on $S$ can be extended to an ultrafilter on $S$

Lemma: If $C$ is a subset of filters on $S$ and if every $F_{1}, F_{2} \in C$ either $F_{1} \subseteq F_{2}$ or $F_{2} \subseteq F_{1}$ , then the union of $C$ is also a filter on $S$

There is a natural relation between ultrafilters and Measures. Let us call a content $m$ on $S$ two-valued if it only takes values $0$ or $1$ ; for every $A \subseteq S$ , $m (A) \in {0, 1}$ .

Th:

If $m$ is a two-valued content on $S$ then $U = {A \subseteq S ∣ m (A) = 1} = m^{- 1} [{1}]$ is an ultrafilter
If $U$ is an ultrafilter on $S$ , then the function $m : P (S) \to {0, 1} = 2$ defined as $m (A) = 1$ if $A \in U$ , and $m (A) = 0$ if $A \notin U$ , is a two valued content on $S$ .

Prop: A nonprincipal ultrafilter is free. Meaning a ultrafilter is nonprincipal iff it is free.

Cor: An ultrafilter is nonprincipal iff doesn't contain a finite subset of $X$ .

Th: Let $X$ be a set, if $X$ is finite there are $| X |$ ultrafilters, if $X$ is infinite, there are $2^{2^{| X |}}$ ultrafilters

Cor: if $X$ is infinite, there are $2^{2^{| X |}}$ nonprincipal ultrafilters

Def: A nonempty family $U$ of subsets of $X$ is called ultra if $\emptyset \notin U$ and for every $S \subseteq X$ , there exists $B \in U$ , such that $B \subseteq S$ or $B \subseteq X ∖ S$ (or equivalently such that $B \cap S = B$ or $B \cap S = \emptyset$ )

Prop: A nonempty family $U$ of subsets of $X$ is called ultra if $\emptyset \notin U$ and any of the following equivalent are satisfied:

For every set $S \subseteq X$ there exists $B \in U$ such that $B \cap S = B$ or $B \cap S = \emptyset$
For every $S \subseteq ⋃ U$ there exists $B \in U$ such that $B \cap S = B$ or $B \cap S = \emptyset$
For every set $S$ , there exists $B \in U$ such that $B \cap S = B$ or $B \cap S = \emptyset$
The last two characterizations we see that don't depend on $X$ , so we see that $U$ is ultra is independent of the set $X$

We see that a ultrafilter is a filter that is ultra.

Def: An ultra prefilter is a filter base that is ultra.

Prop: A maximal prefilter on $X$ is a prefilter $U$ on $X$ that satisfies any of the following equivalent conditions:

$U$ is ultra
$U$ is maximal with respect to the preorder of prefilters
if a filter $F$ on $X$ satisfies that $U \leq F$ then $F \leq U$ (using the preorder on the prefilters)
the filter generated by $U$ is ultra