Examples of filters over the natural numbers

100 Views Asked by At

Given a set $X$, we can define a filter $F \subseteq 2^{X}$ (here $2^{X}$ means the powerset of $X$) as a family of sets that have the following properties:

(i) $F \not= \emptyset$

(ii) If $S_{1}, S_{2} \in F$ then $S_{1} \cap S_{2} \in F$

(iii) If $S_{1} \subseteq S_{2} \subseteq X$ and $S_{1} \in F$ then $S_{2} \in F$

I'm having a hard time coming up with filters over the natural numbers, we saw one example in the book which is called the Frechet filter defined as $F = \{S \in 2^{\mathbb{N}} : S^{c} \text{ is finite}\}$ Here $S^{c}$ means $\mathbb{N} \setminus S$. It's easy to see that this is a filter using properties of sets, but I can't come up with any other filter over the natural numbers, it just seems so abstract.

2

There are 2 best solutions below

6
On BEST ANSWER

A classical silly example is a principal (ultra)filter for a point $p \in \mathbb{N}$, i.e. the filter of the form $$ F_p = \left\{ S \subseteq \mathbb{N} : p \in S \right\} . $$ More generally, if $A \subseteq \mathbb{N}$ is any subset of $\mathbb{N}$, then you can define the filter $$\left\{ S \subseteq \mathbb{N} : A \subseteq S \right\}.$$ Another silly example would be the power set of $\mathbb{N}$, which is the special case of the previous example you get when you take $A = \emptyset$.

Another way of constructing filters is this: If you have a filter $F$ and some $E \subseteq \mathbb{N}$ such that $E, E^\complement \not \in F$, then you can look at the filter $$F \cup \left\{ S \cup E : S \in F \right\} ,$$ which you can think of as the filter you get when you take $F$ and append $E$ to it.

EDIT: My last section about $F \cup \left\{ S \cup E : S \in F \right\}$ is not, I don't think, true in general. Thank you to @Andreas Blass whose prodding prompted me to revisit this. There is, in general, a way to talk about a filter "generated by" some set $\mathcal{H} \subseteq 2^X$. Write $$\mathcal{F}^\mathcal{H} = \left\{ A : \exists B_1, \ldots, B_n \in \mathcal{H} \; \left( A \supseteq B_1 \cap \cdots \cap B_n \right) \right\} .$$

You can check that this defines a filter, and that $\mathcal{F}^\mathcal{H} \supseteq \mathcal{H}$. Less obvious, but still elementary to check, is that this is the smallest filter that contains $\mathcal{H}$. This ties into another construction of filters: If $\mathscr{F}$ is some family of filters on $X$, then $\bigcap_{F \in \mathscr{F}} F$ is also a filter on $X$ (take this as an exercise). You can check that if $\mathscr{F}^\mathcal{H}$ denotes the family of all filters on $X$ that contain $\mathcal{H}$, then $\mathcal{F}^\mathcal{H} = \bigcap_{F \in \mathscr{F}^\mathcal{H}} F$. Here's a quick sketch of the proof: On one hand, if $F \in \mathscr{F}^\mathcal{H}$, then $\mathcal{F}^\mathcal{H} \subseteq F$, so $\mathcal{F}^\mathcal{H} \subseteq \bigcap_{F \in \mathscr{F}^\mathcal{H}} F$. In the other direction, we can see that $\mathcal{F}^\mathcal{H} \in \mathscr{F}^\mathcal{H}$, so $\mathcal{F}^\mathcal{H} \supseteq \bigcap_{F \in \mathscr{F}^\mathcal{H}} F$.

0
On

A couple of other examples: Define the density of a subset $A\subseteq\mathbb N$ to be the limit of $\displaystyle{\frac{|A\cap\{0,1,\dots,n-1\}|}n}$ as $n\to\infty$ (provided the limit exists). Then the sets $A$ of density $1$ constitute a filter.

The sets $A\subseteq\mathbb N$ for which $\sum_{n\notin A}\frac1n$ converges form a filter.

Once you've seen these examples, you can probably produce plenty of similar ones.