0
$\begingroup$

Let $X$ be an infinite set. A nonempty collection of subsets, say $F$, of $X$ is called a filter if

$\emptyset \notin F$

$A, B \in F$ implies $A \cap B \in F$

$A \in F$, $A \subseteq B$ implies $B \in F$

and is called an ultrafilter if in addition,

for all $A \subseteq X$, $A \in F$ or $A^c \in F$

holds.

A (ultra)filter is called free if for all $a \in X$, $\{a\} \notin F$.

I want to prove that every free filter $F$ is contained in a free ultrafilter.

My try: I tried to use Zorn's lemma to the collection $\mathcal C := \{A: A$ is a free filter containing $F \}$. However, I can't prove that the maximal element $U$ is an ultrafilter.

If $U$ were not an ultrafilter, there will exist an $A \neq \emptyset$ such that $A$, $A^c \notin U$. Then we will be able to extend $U \cup \{ A \}$ into a filter. However, I cannot prove that this filter is free, so that it contradicts the maximality of $U$.

Thank you!

$\endgroup$
2
  • 3
    $\begingroup$ Actually, that is not the definition of free in the general case of filters. A filter $F$ is free if $\bigcap F\notin F$. In the ultrafilter case it coincides with your definition. $\endgroup$
    – Asaf Karagila
    Jan 31, 2020 at 9:01
  • $\begingroup$ Without changed definition of free, this is false: a "free" filter that contains a finite subset, does not have such an extension. See my answer for that. $\endgroup$ Feb 2, 2020 at 12:16

4 Answers 4

3
$\begingroup$

First of all, as Asaf Karaglia wrote, a filter $\mathscr F$ is free if $\,\bigcap \mathscr F \not\in\mathscr F$. Clearly, a free filter does not possess finite sets.

It is not hard to show that, if a filter $\mathscr{F}$ is free, then adding to it all the complements of finite sets of $X$, and taking all the the finite intersections of its sets, you produce another free filter $\mathscr{F}'\supset\mathscr{F}$.

Using the Zorn's Lemma, on the filters, bigger than $\mathscr F'$, you obtain an ultrafilter which does not contain finite sets, and hence it is a free ultrafilter.

$\endgroup$
1
  • $\begingroup$ Thanks for your elaboration. Now I am confused since a different answer and the Wikipedia('filter' page) says that a filter is free if its intersection is empty. Is this equivalent to your and Asaf's definition? $\endgroup$
    – Moca Aoba
    Jan 31, 2020 at 13:35
2
$\begingroup$

In the poset of all filters (extending $\mathcal{F}$) under inclusion, a maximal element is an ultrafilter in your sense:

Suppose $\mathcal{M}$ is maximal and extends $\mathcal{F}$, and $A \subseteq X$ and $A \notin \mathcal{M}$, then suppose there some $B \in \mathcal{M}$ exists with $A \cap B = \emptyset$. Then $B \subseteq A^\complement$ and so $A^\complement \in \mathcal{M}$ and we're done. If this is not the case, i.e. $$\forall B \in \mathcal{M}: B \cap A \neq \emptyset\tag{1}$$

then we can define $$\mathcal{M}' = \{B \subseteq X: \exists C \in \mathcal{M}: C \cap A \subseteq B\}\tag{2}$$ and $(2)$ defines a filter that extends $\mathcal{M}$ (so $\mathcal{F}$ too) and contains $A$, so $\mathcal{M} \subsetneq \mathcal{M}'$, contradicting maximality of $\mathcal{M}$. So the second case does not occur and we're done showing $\mathcal{M}$ is an ultrafilter.

Now, the question of being free is a definitional matter: usually this is defined to mean (for any filter) that $\bigcap \mathcal{F} \notin \mathcal{F}$ and for your notion of ultrafilter this is equivalent: if $\mathcal{M}$ is an ultrafilter, $\{a\} \in \mathcal{M}$ iff $\{a\} = \bigcap \mathcal{M}$ iff $\mathcal{M} = \{A \subseteq X: a \in M\}=: \mathcal{M}_a$.

If $\mathcal{F} \subseteq \mathcal{M}$ and $\{a\} \in \mathcal{M}$ this implies that $A \in \mathcal{F} \to A \in \mathcal{M} \to \{a\} \cap A \neq \emptyset \to a \in A$, so $a \in \bigcap \mathcal{F}$. But this is not a direct contradiction with being free in your sense. In fact if $\mathcal{F}$ are all supersets of the even integers in the set of all integers $X$, then it is free in your sense but one possible extension that is maximal is all subsets that contain $0$, which is not free in your sense. So there is no insurance directly that we'll get a free ultrafilter from a free starting filter. But this can be helped if $\mathcal{F}$ contains no finite subset: in that case define $$\mathcal{F}' = \{C \subseteq X: \exists F \in \mathcal{F} \exists P \subseteq X \text { finite }: (F\setminus P) \subseteq C\}\tag{3}$$

and check that $\mathcal{F}'$ defines a filter on $X$ that extends $\mathcal{F}$ and then check that any maximal filter that extends $\mathcal{F}'$ is a free ultrafilter extending $\mathcal{F}$.

if however $\mathcal{F}$ contains a finite subset there can be no free ultrafilter extending it:

Let $A \in \mathcal{F}$ be finite, say $A=\{a_1, a_2, \ldots, a_n\}$. If $\mathcal{M}$ extends $\mathcal{F}$ and is free, $\{a_i\}^\complement \in \mathcal{M}$ for $i=1,\ldots,n$ and so $A^\complement = \bigcap_{i=1}^n \{a_i\}^\complement \in \mathcal{M}$ as filters are closed under finite intersections, contradicting $A \in \mathcal{M}$ (as $\mathcal{M}$ extends $\mathcal{F}$). So $$\mathcal{F}= \{A \subseteq \Bbb N: \{0,1,2\} \subseteq A\}$$

is a counterexample to your statement. Unless you redefine "free" of course.

$\endgroup$
1
$\begingroup$

With Axiom of choice yes, without Axiom of choice is this undecidable. For a filter $\mathcal{F} $, the system of filters $\mathcal{F}\subseteq \mathcal{F}'$ not containing finite set satisfies that for any chain $$ \mathcal{F}\subseteq \mathcal{F}_1\subseteq \mathcal{F}_2\subseteq \mathcal{F}_3\text{...} $$

(may be uncountable)

the union of them is also filter not containing finite set. So, by Zorn's lemma (equivalent to Axiom of choice!) there exist a maximal element of all filters $\mathcal{F}\subseteq \mathcal{F}'$ and must be ultrafilter.

$\endgroup$
1
$\begingroup$

A filter is free iff it contains the Fréchet filter, so every filter extending a free filter is free.

Alternatively a filter $G$ is free iff $\bigcap G=\varnothing$. Let $F$ be the filter generated by $A\cup U$. Since $\bigcap U=\varnothing$ and $U\subseteq F$ we also have $\bigcap F=\varnothing$.

Also note that your definition of free works fine for ultrafilters, since an ultrafilter containing a finite set contains a singleton, but not for filters, for example the filter $\{A\subseteq\omega\mid\{3,4\}\subseteq A\}$ contains no singletons, but is not free.

$\endgroup$
2
  • $\begingroup$ What is the most standard definition, which works for both filter and ultrafilters, of being free? I am totally new to the concept and am confused by the various definitions provided in the literature. $\endgroup$
    – Moca Aoba
    Jan 31, 2020 at 8:58
  • $\begingroup$ @JohnDoe usually one of the two characterizations I used in my answer is given as definition and the other is proved to be equivalent $\endgroup$ Jan 31, 2020 at 9:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .