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
1
$\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.