Filter on a set

For filters on a poset, see Filter (mathematics).

For other uses, see Filter (disambiguation).

In mathematics, a filter on a set is a family of subsets which is closed under supersets and finite intersections. The concept originates in topology, where the neighborhoods of a point form a filter on the space. Filters were introduced by Henri Cartan in 1937^[1][2] and, as described in the article dedicated to filters in topology, they were subsequently used by Nicolas Bourbaki in their book Topologie Générale as an alternative to the related notion of a net developed in 1922 by E. H. Moore and Herman L. Smith. They have also found applications in model theory and set theory.

Filters on a set were later generalized to order filters. Specifically, a filter on a set ${\displaystyle X}$ is a order filter on the power set of ${\displaystyle X}$ ordered by inclusion.

The notion dual to a filter is an ideal. Ultrafilters are a particularly important subclass of filters.

Definition

Given a set ${\displaystyle X}$, a filter ${\displaystyle {\mathcal {F}}}$ on ${\displaystyle X}$ is a set of subsets of ${\displaystyle X}$ such that:^[3][4][5]

• ${\displaystyle F}$ is upwards-closed: If ${\displaystyle A,B\subseteq X}$ are such that ${\displaystyle A\in {\mathcal {F}}}$ and ${\displaystyle A\subseteq B}$ then ${\displaystyle B\in {\mathcal {F}}}$,
• ${\displaystyle F}$ is closed under finite intersections: ${\displaystyle X\in {\mathcal {F}}}$,^[a], and if ${\displaystyle A\in {\mathcal {F}}}$ and ${\displaystyle B\in {\mathcal {F}}}$ then ${\displaystyle A\cap B\in {\mathcal {F}}}$.

A proper (or non-degenerate) filter is a filter which is proper as a subset of the powerset ${\displaystyle {\mathcal {P}}(X)}$ (i.e., the only improper filter is ${\displaystyle {\mathcal {P}}(X)}$, consisting of all possible subsets). By upwards-closure, a filter is proper if and only if it does not contain the empty set.^[4] Many authors adopt the convention that a filter must be proper by definition.^[6][7][8][9]

When ${\displaystyle {\mathcal {F}}}$ and ${\displaystyle {\mathcal {G}}}$ are two filters on the same set such that ${\displaystyle {\mathcal {F}}\subseteq {\mathcal {G}}}$ holds, ${\displaystyle {\mathcal {F}}}$ is said to be coarser^[10] than ${\displaystyle {\mathcal {G}}}$ (or a subfilter of ${\displaystyle {\mathcal {G}}}$) while ${\displaystyle {\mathcal {G}}}$ is said to be finer^[10] than ${\displaystyle {\mathcal {F}}}$ (or subordinate to ${\displaystyle {\mathcal {F}}}$ or a superfilter^[11] of ${\displaystyle {\mathcal {F}}}$).

Examples

• The singleton set ${\displaystyle {\mathcal {F}}=\{X\}}$ is called the trivial or indiscrete filter on ${\displaystyle X}$.^[12]
• If ${\displaystyle Y}$ is a subset of ${\displaystyle X}$, the subsets of ${\displaystyle X}$ which are supersets of ${\displaystyle Y}$ form a principal filter.^[3]
• If ${\displaystyle X}$ is a topological space and ${\displaystyle x\in X}$, then the set of neighborhoods of ${\displaystyle x}$ is a filter on ${\displaystyle X}$, the neighborhood filter^[13] or vicinity filter^[14] of ${\displaystyle x}$.
• Many examples arise from various "largeness" conditions:
  • If ${\displaystyle X}$ is a set, the set of all cofinite subsets of ${\displaystyle X}$ (i.e., those sets whose complement in ${\displaystyle X}$ is finite) is a filter on ${\displaystyle X}$, the Fréchet filter^[12][15][5] (or cofinite filter^[13]).
  • Similarly, if ${\displaystyle X}$ is a set, the cocountable subsets of ${\displaystyle X}$ (those whose complement is countable) form a filter, the cocountable filter^[14] which is finer than the Fréchet filter. More generally, for any cardinal ${\displaystyle \kappa }$, the subsets whose complement has cardinal at most ${\displaystyle \kappa }$ form a filter.
  • If ${\displaystyle X}$ is a metric space, e.g., ${\displaystyle \mathbb {R} ^{n}}$, the co-bounded subsets of ${\displaystyle X}$ (those whose complement is bounded set) form a filter on ${\displaystyle X}$.^[16]
  • If ${\displaystyle X}$ is a complete measure space (e.g., ${\displaystyle \mathbb {R} ^{n}}$ with the Lebesgue measure), the conull subsets of ${\displaystyle X}$, i.e., the subsets whose complement has measure zero, form a filter on ${\displaystyle X}$. (For a non-complete measure space, one can take the subsets which, while not necessarily measurable, are contained in a measurable subset of measure zero.)
  • Similarly, if ${\displaystyle X}$ is a measure space, the subsets whose complement is contained in a measurable subset of finite measure form a filter on ${\displaystyle X}$.
  • If ${\displaystyle X}$ is a topological space, the comeager subsets of ${\displaystyle X}$, i.e., those whose complement is meager, form a filter on ${\displaystyle X}$.
  • The subsets of ${\displaystyle \mathbb {N} }$ which have a natural density of 1 form a filter on ${\displaystyle \mathbb {N} }$.^[17]
• The club filter of a regular uncountable cardinal ${\displaystyle \kappa }$ is the filter of all sets containing a club subset of ${\displaystyle \kappa }$.
• If ${\displaystyle ({\mathcal {F}}_{i})_{i\in I}}$ is a family of filters on ${\displaystyle X}$ and ${\displaystyle {\mathcal {J}}}$ is a filter on ${\displaystyle I}$ then ${\displaystyle \bigcup _{A\in {\mathcal {J}}}\bigcap _{i\in A}{\mathcal {F}}_{i}}$ is a filter on ${\displaystyle X}$ called Kowalsky's filter.^[18]

Principal and free filters

The kernel of a filter ${\displaystyle {\mathcal {F}}}$ on ${\displaystyle X}$ is the intersection of all the subsets of ${\displaystyle X}$ in ${\displaystyle F}$.

A filter ${\displaystyle {\mathcal {F}}}$ on ${\displaystyle X}$ is principal^[3] (or atomic^[13]) when it has a particularly simple form: it contains exactly the supersets of ${\displaystyle Y}$, for some fixed subset ${\displaystyle Y\subseteq X}$. When ${\displaystyle Y=\varnothing }$, this yields the improper filter. When ${\displaystyle Y=\{y\}}$ is a singleton, this filter (which consists of all subsets that contain ${\displaystyle y}$) is called the fundamental filter^[3] (or discrete filter^[19]) associated with ${\displaystyle y}$.

A filter ${\displaystyle {\mathcal {F}}}$ is principal if and only if the kernel of ${\displaystyle {\mathcal {F}}}$ is an element of ${\displaystyle {\mathcal {F}}}$, and when this is the case, ${\displaystyle {\mathcal {F}}}$ consists of the supersets of its kernel.^[20] On a finite set, every filter is principal (since the intersection defining the kernel is finite).

A filter is said to be free when it has empty kernel, otherwise it is fixed (and if ${\displaystyle x}$ is an element of the kernel, it is fixed by ${\displaystyle x}$).^[21] A filter on a set ${\displaystyle X}$ is free if and only if it contains the Fréchet filter on ${\displaystyle X}$.^[22]

Two filters ${\displaystyle {\mathcal {F}}_{1}}$ and ${\displaystyle {\mathcal {F}}_{2}}$ on ${\displaystyle X}$ mesh when every member of ${\displaystyle {\mathcal {F}}_{1}}$ intersects every member of ${\displaystyle {\mathcal {F}}_{2}}$.^[23] For every filter ${\displaystyle {\mathcal {F}}}$ on ${\displaystyle X}$, there exists a unique pair of filters ${\displaystyle {\mathcal {F}}_{f}}$ (the free part of ${\displaystyle {\mathcal {F}}}$) and ${\displaystyle {\mathcal {F}}_{p}}$ (the principal part of ${\displaystyle {\mathcal {F}}}$) on ${\displaystyle X}$ such that ${\displaystyle {\mathcal {F}}_{f}}$ is free, ${\displaystyle {\mathcal {F}}_{p}}$ is principal, ${\displaystyle {\mathcal {F}}_{f}\cap {\mathcal {F}}_{p}={\mathcal {F}}}$, and ${\displaystyle {\mathcal {F}}_{p}}$ does not mesh with ${\displaystyle {\mathcal {F}}_{f}}$. The principal part ${\displaystyle {\mathcal {F}}_{p}}$ is the principal filter generated by the kernel of ${\displaystyle {\mathcal {F}}}$, and the free part ${\displaystyle {\mathcal {F}}_{f}}$ consists of elements of ${\displaystyle {\mathcal {F}}}$ with any number of elements from the kernel possibly removed.^[22]

A filter ${\displaystyle {\mathcal {F}}}$ is countably deep if the kernel of any countable subset of ${\displaystyle {\mathcal {F}}}$ belongs to ${\displaystyle {\mathcal {F}}}$.^[14]

Correspondence with order filters

The concept of a filter on a set is a special case of the more general concept of a filter on a partially ordered set. By definition, a filter on a partially ordered set ${\displaystyle P}$ is a subset ${\displaystyle F}$ of ${\displaystyle P}$ which is upwards-closed (if ${\displaystyle x\in F}$ and ${\displaystyle x\leq y}$ then ${\displaystyle y\in F}$) and downwards-directed (every finite subset of ${\displaystyle F}$ has a lower bound in ${\displaystyle F}$). A filter on a set ${\displaystyle X}$ is the same as a filter on the powerset ${\displaystyle {\mathcal {P}}(X)}$ ordered by inclusion.^[b]

Constructions of filters

Intersection of filters

If ${\displaystyle ({\mathcal {F}}_{i})_{i\in I}}$ is a family of filters on ${\displaystyle X}$, its intersection ${\displaystyle \bigcap _{i\in I}{\mathcal {F}}_{i}}$ is a filter on ${\displaystyle X}$. The intersection is a greatest lower bound operation in the set of filters on ${\displaystyle X}$ partially ordered by inclusion, which endows the filters on ${\displaystyle X}$ with a complete lattice structure.^[14][24]

The intersection ${\displaystyle \bigcap _{i\in I}{\mathcal {F}}_{i}}$ consists of the subsets which can be written as ${\displaystyle \bigcup _{i\in I}A_{i}}$ where ${\displaystyle A_{i}\in {\mathcal {F}}_{i}}$ for each ${\displaystyle i\in I}$.

Filter generated by a family of subsets

Given a family of subsets ${\displaystyle {\mathcal {S}}\subseteq {\mathcal {P}}(X)}$, there exists a minimum filter on ${\displaystyle X}$ (in the sense of inclusion) which contains ${\displaystyle {\mathcal {S}}}$. It can be constructed as the intersection (greatest lower bound) of all filters on ${\displaystyle X}$ containing ${\displaystyle {\mathcal {S}}}$. This filter ${\displaystyle \langle {\mathcal {S}}\rangle }$ is called the filter generated by ${\displaystyle {\mathcal {S}}}$, and ${\displaystyle {\mathcal {S}}}$ is said to be a filter subbase of ${\displaystyle \langle {\mathcal {S}}\rangle }$. ^[25]

The generated filter can also be described more explicitly: ${\displaystyle \langle {\mathcal {S}}\rangle }$ is obtained by closing ${\displaystyle {\mathcal {S}}}$ under finite intersections, then upwards, i.e., ${\displaystyle \langle {\mathcal {S}}\rangle }$ consists of the subsets ${\displaystyle Y\subseteq X}$ such that ${\displaystyle A_{0}\cap \dots \cap A_{n-1}\subseteq Y}$ for some ${\displaystyle A_{0},\dots ,A_{n-1}\in {\mathcal {B}}}$.^[11]

Since these operations preserve the kernel, it follows that ${\displaystyle \langle {\mathcal {S}}\rangle }$ is a proper filter if and only if ${\displaystyle {\mathcal {S}}}$ has the finite intersection property: the intersection of a finite subfamily of ${\displaystyle {\mathcal {S}}}$ is non-empty.^[16]

In the complete lattice of filters on ${\displaystyle X}$ ordered by inclusion, the least upper bound of a family of filters ${\displaystyle ({\mathcal {F}}_{i})_{i\in I}}$ is the filter generated by ${\displaystyle \bigcup _{i\in I}{\mathcal {F}}_{i}}$.^[20]

Two filters ${\displaystyle {\mathcal {F}}_{1}}$ and ${\displaystyle {\mathcal {F}}_{2}}$ on ${\displaystyle X}$ mesh if and only if ${\displaystyle \langle {\mathcal {F}}_{1}\cup {\mathcal {F}}_{2}\rangle }$ is proper.^[23]

Filter bases

Let ${\displaystyle {\mathcal {F}}}$ be a filter on ${\displaystyle X}$. A filter base of ${\displaystyle {\mathcal {F}}}$ is a family of subsets ${\displaystyle {\mathcal {B}}\subseteq {\mathcal {P}}(X)}$ such that ${\displaystyle {\mathcal {F}}}$ is the upwards closure of ${\displaystyle {\mathcal {B}}}$, i.e., ${\displaystyle {\mathcal {F}}}$ consists of those subsets ${\displaystyle Y\subseteq X}$ for which ${\displaystyle A\subseteq Y}$ for some ${\displaystyle A\in {\mathcal {B}}}$.^[6]

This upwards closure is a filter if and only if ${\displaystyle {\mathcal {B}}}$ is downwards-directed, i.e., ${\displaystyle {\mathcal {B}}}$ is non-empty and for all ${\displaystyle A,B\in {\mathcal {B}}}$ there exists ${\displaystyle C\in {\mathcal {B}}}$ such that ${\displaystyle C\subseteq A\cap B}$.^[6][13] When this is the case, ${\displaystyle {\mathcal {B}}}$ is also called a prefilter, and the upwards closure is also equal to the generated filter ${\displaystyle \langle {\mathcal {B}}\rangle }$.^[16] Hence, being a filter base of ${\displaystyle {\mathcal {F}}}$ is a stronger property than being a filter subbase of ${\displaystyle {\mathcal {F}}}$.

Examples

• When ${\displaystyle X}$ is a topological space and ${\displaystyle x\in X}$, a filter base of the neighborhood filter of ${\displaystyle x}$ is known as a neighborhood base for ${\displaystyle x}$, and similarly, a filter subbase of the neighborhood filter of ${\displaystyle x}$ is known as a neighborhood subbase for ${\displaystyle x}$. The open neighborhoods of ${\displaystyle x}$ always form a neighborhood base for ${\displaystyle x}$, by definition of the neighborhood filter. In ${\displaystyle X=\mathbb {R} ^{n}}$, the closed balls of positive radius around ${\displaystyle x}$ also form a neighborhood base for ${\displaystyle x}$.
• Let ${\displaystyle X}$ be an infinite set and let ${\displaystyle {\mathcal {F}}}$ consist of the subsets of ${\displaystyle X}$ which contain all points but one. Then ${\displaystyle {\mathcal {F}}}$ is a filter subbase of the Fréchet filter on ${\displaystyle X}$, which consists of the cofinite subsets. Its closure under finite intersections is the entire Fréchet filter, but there are smaller bases of the Fréchet filter which contain the subbase ${\displaystyle {\mathcal {F}}}$, such as the one formed by the subsets of ${\displaystyle X}$ which contain all points but a finite odd number. In fact, for every base of the Fréchet filter, removing any subset yields another base of the Fréchet filter.
• If ${\displaystyle X}$ is a topological space, the dense open subsets of ${\displaystyle X}$ form a filter base on ${\displaystyle X}$, because they are closed under finite intersection. The filter they generate consists of the complements of nowhere dense subsets. On ${\displaystyle X=\mathbb {R} ^{n}}$, restricting to the null dense open subsets yields another filter base for the same filter.^{[citation needed]}
• Similarly, if ${\displaystyle X}$ is a topological space, the countable intersections of dense open subsets form a filter base which generates the filter of comeager subsets.
• Let ${\displaystyle X}$ be a set and let ${\displaystyle (x_{i})_{i\in I}}$ be a net with values in ${\displaystyle X}$, i.e., a family whose domain ${\displaystyle I}$ is a directed set. The filter base of tails of ${\displaystyle (x_{i})}$ consists of the sets ${\displaystyle \{x_{j},j\geq i\}}$ for ${\displaystyle i\in I}$; it is downwards-closed by directedness of ${\displaystyle I}$. The generated filter is called the eventuality filter or filter of tails of ${\displaystyle (x_{n})}$. A sequential filter^[26] or elementary filter^[9] is a filter which is the eventuality filter of some net. This example is fundamental in the application of filters in topology.^[13][27]
• Every π-system is a filter base.

Trace of a filter on a subset

If ${\displaystyle {\mathcal {F}}}$ is a filter on ${\displaystyle X}$ and ${\displaystyle Y\subseteq X}$, the trace of ${\displaystyle {\mathcal {F}}}$ on ${\displaystyle Y}$ is ${\displaystyle \{A\cap Y,A\in {\mathcal {F}}\}}$, which is a filter.^[15]

Image of a filter by a function

Let ${\displaystyle f:X\to Y}$ be a function.

When ${\displaystyle {\mathcal {F}}}$ is a family of subsets of ${\displaystyle X}$, its image by ${\displaystyle f}$ is defined as

$${\displaystyle f({\mathcal {F}})=\{\{f(x),x\in A\},A\in {\mathcal {F}}\}}$$

The image filter by ${\displaystyle f}$ of a filter ${\displaystyle {\mathcal {F}}}$ on ${\displaystyle X}$ is defined as the generated filter ${\displaystyle \langle f({\mathcal {F}})\rangle }$.^[28] If ${\displaystyle f}$ is surjective, then ${\displaystyle f({\mathcal {F}})}$ is already a filter. In the general case, ${\displaystyle f({\mathcal {F}})}$ is a filter base and hence ${\displaystyle \langle f({\mathcal {F}})\rangle }$ is its upwards closure.^[29] Furthermore, if ${\displaystyle {\mathcal {B}}}$ is a filter base of ${\displaystyle {\mathcal {F}}}$ then ${\displaystyle f({\mathcal {B}})}$ is a filter base of ${\displaystyle \langle f({\mathcal {F}})\rangle }$.

The kernels of ${\displaystyle {\mathcal {F}}}$ and ${\displaystyle \langle f({\mathcal {F}})\rangle }$ are linked by ${\displaystyle f\left(\bigcap {\mathcal {F}}\right)\subseteq \bigcap \langle f({\mathcal {F}})\rangle }$.

Product of filters

Given a family of sets ${\displaystyle (X_{i})_{i\in I}}$ and a filter ${\displaystyle {\mathcal {F}}_{i}}$ on each ${\displaystyle X_{i}}$, the product filter ${\displaystyle \prod _{i\in I}{\mathcal {F}}_{i}}$ on the product set ${\displaystyle \prod _{i\in I}X_{i}}$ is defined as the filter generated by the sets ${\displaystyle \pi _{i}^{-1}(A)}$ for ${\displaystyle i\in I}$ and ${\displaystyle A\in {\mathcal {F}}_{i}}$, where ${\displaystyle \pi _{i}:\left(\prod _{j\in I}X_{j}\right)\to X_{i}}$ is the projection from the product set onto the ${\displaystyle i}$-th component.^[12][30] This construction is similar to the product topology.

If each ${\displaystyle {\mathcal {B}}_{i}}$ is a filter base on ${\displaystyle {\mathcal {F}}_{i}}$, a filter base of ${\displaystyle \prod _{i\in I}{\mathcal {F}}_{i}}$ is given by the sets ${\displaystyle \prod _{i\in I}A_{i}}$ where ${\displaystyle (A_{i})}$ is a family such that ${\displaystyle A_{i}\in {\mathcal {F}}_{i}}$ for all ${\displaystyle i\in I}$ and ${\displaystyle A_{i}=X_{i}}$ for all but finitely many ${\displaystyle i\in I}$.^[12][31]

See also

• Axiomatic foundations of topological spaces, for a definition of topological spaces in terms of filters
• Filters in topology – Use of filters to describe and characterize all basic topological notions and results
• Convergence space, a generalization of topological spaces using filters
• Filter quantifier
• Ultrafilter – Maximal proper filter
• Generic filter, a kind of filter used in set-theoretic forcing

Notes

1. The intersection of zero subsets of ${\displaystyle X}$ is ${\displaystyle X}$ itself.
2. It is immediate that a filter on ${\displaystyle X}$ is an order filter on ${\displaystyle {\mathcal {P}}(X)}$. For the converse, let ${\displaystyle {\mathcal {F}}}$ be an order filter on ${\displaystyle {\mathcal {P}}(X)}$. It is upwards-closed by definition. We check closure under finite intersections. If ${\displaystyle A_{0},\dots ,A_{n-1}}$ is a finite family of subsets from ${\displaystyle {\mathcal {F}}}$, it has a lower bound in ${\displaystyle {\mathcal {F}}}$ by downwards-closure, which is some ${\displaystyle B\in {\mathcal {F}}}$ such that ${\displaystyle B\subseteq A_{0},\dots ,B\subseteq A_{n-1}}$. Then ${\displaystyle B\subseteq A_{0}\cap \dots \cap A_{n-1}}$, hence ${\displaystyle A_{0}\cap \dots \cap A_{n-1}\in {\mathcal {F}}}$ by upwards-closure.