Filter (mathematics)

In mathematics, a filter or order filter is a special subset of a partially ordered set (poset). Filters appear in order and lattice theory, but can also be found in topology, from which they originate. The dual notion of a filter is an order ideal.

Filters on sets 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. Order filters are generalizations of this notion from sets to the more general setting of partially ordered sets. For information on order filters in the special case where the poset consists of the power set ordered by set inclusion, see the article Filter (set theory).

Motivation

1. Intuitively, a filter in a partially ordered set (poset), $P,$ is a subset of $P$ that includes as members those elements that are large enough to satisfy some given criterion. For example, if $x$ is an element of the poset, then the set of elements that are above $x$ is a filter, called the principal filter at $x.$ (If $x$ and $y$ are incomparable elements of the poset, then neither of the principal filters at $x$ and $y$ is contained in the other one, and conversely.)

Similarly, a filter on a set contains those subsets that are sufficiently large to contain some given thing. For example, if the set is the real line and $x$ is one of its points, then the family of sets that include $x$ in their interior is a filter, called the filter of neighbourhoods of $x.$ The thing in this case is slightly larger than $x,$ but it still does not contain any other specific point of the line.

The above interpretations explain conditions 1 and 3 in the section General definition: Clearly the empty set is not "large enough", and clearly the collection of "large enough" things should be "upward-closed". However, they do not really, without elaboration, explain condition 2 of the general definition. For, why should two "large enough" things contain a common "large enough" thing?

2. Alternatively, a filter can be viewed as a "locating scheme": When trying to locate something (a point or a subset) in the space $X,$ call a filter the collection of subsets of $X$ that might contain "what is looked for". Then this "filter" should possess the following natural structure:

A locating scheme must be non-empty in order to be of any use at all.
If two subsets, $E$ and $F,$ both might contain "what is looked for", then so might their intersection. Thus the filter should be closed with respect to finite intersection.
If a set $E$ might contain "what is looked for", so does every superset of it. Thus the filter is upward-closed.

An ultrafilter can be viewed as a "perfect locating scheme" where each subset $E$ of the space $X$ can be used in deciding whether "what is looked for" might lie in $E.$

From this interpretation, compactness (see the mathematical characterization below) can be viewed as the property that "no location scheme can end up with nothing", or, to put it another way, "always something will be found".

The mathematical notion of filter provides a precise language to treat these situations in a rigorous and general way, which is useful in analysis, general topology and logic.

3. A common use for a filter is to define properties that are satisfied by "almost all" elements of some topological space $X.$ ^[3] The entire space $X$ definitely contains almost-all elements in it; If some $E\subseteq X$ contains almost all elements of $X,$ then any superset of it definitely does; and if two subsets, $E$ and $F,$ contain almost-all elements of $X,$ then so does their intersection. In a measure-theoretic terms, the meaning of " $E$ contains almost-all elements of $X$ " is that the measure of $X\smallsetminus E$ is 0.

General definition: Filter on a partially ordered set

A subset $F$ of a partially ordered set $(P,\leq )$ is an order filter or dual ideal if the following conditions hold:

$F$ is non-empty.
$F$ is downward directed: For every $x,y\in F,$ there is some $z\in F$ such that $z\leq x$ and $z\leq y.$
$F$ is an upper set or upward-closed: For every $x\in F$ and $p\in P,$ $x\leq p$ implies that $p\in F.$

$F$ is said to be a proper filter if in addition $F$ is not equal to the whole set $P.$ Depending on the author, the term filter is either a synonym of order filter or else it refers to a proper order filter. This article defines filter to mean order filter.

While the above definition is the most general way to define a filter for arbitrary posets, it was originally defined for lattices only. In this case, the above definition can be characterized by the following equivalent statement: A subset $F$ of a lattice $(P,\leq )$ is a filter, if and only if it is a non-empty upper set that is closed under finite infima (or meets), that is, for all $x,y\in F,$ it is also the case that $x\wedge y\in F.$ ^[4] A subset $S$ of $F$ is a filter basis if the upper set generated by $S$ is all of $F.$ Note that every filter is its own basis.

The smallest filter that contains a given element $p\in P$ is a principal filter and $p$ is a principal element in this situation. The principal filter for $p$ is just given by the set $\{x\in P:p\leq x\}$ and is denoted by prefixing $p$ with an upward arrow: $\uparrow p.$

The dual notion of a filter, that is, the concept obtained by reversing all $\,\leq \,$ and exchanging $\,\wedge \,$ with $\,\vee ,$ is ideal. Because of this duality, the discussion of filters usually boils down to the discussion of ideals. Hence, most additional information on this topic (including the definition of maximal filters and prime filters) is to be found in the article on ideals. There is a separate article on ultrafilters.

Applying these definitions to the case where $X$ is a vector space and $P$ is the set of all vector subspaces of $X$ ordered by inclusion $\,\subseteq \,$ gives rise to the notion of linear filters and linear ultrafilters. Explicitly, a linear filter on a vector space $X$ is a family ${\mathcal {B}}$ of vector subspaces of $X$ such that if $A,B\in {\mathcal {B}}$ and if $C$ is a vector subspace of $X$ that contains $A,$ then $A\cap B,C\in {\mathcal {B}}.$ ^[5] A linear filter is called proper if it does not contain $\{0\};$ a linear ultrafilter on $X$ is a maximal proper linear filter on $X.$ ^[5]

Filter on a set

Families ${\mathcal {F}}$ of sets over $\Omega$ v t e
Is necessarily true of ${\mathcal {F}}\colon$ or, is ${\mathcal {F}}$ closed under:	Directed by $\,\supseteq$	$A\cap B$	$A\cup B$	$B\setminus A$	$\Omega \setminus A$	$A_{1}\cap A_{2}\cap \cdots$	$A_{1}\cup A_{2}\cup \cdots$	$\Omega \in {\mathcal {F}}$	$\varnothing \in {\mathcal {F}}$	F.I.P.
$π$ -system
Semiring										Never
Semialgebra (Semifield)										Never
Monotone class						only if $A_{i}\searrow$	only if $A_{i}\nearrow$
𝜆-system (Dynkin System)				only if $A\subseteq B$			only if $A_{i}\nearrow$ or they are disjoint			Never
Ring (Order theory)
Ring (Measure theory)										Never
δ-Ring										Never
𝜎-Ring										Never
Algebra (Field)										Never
𝜎-Algebra (𝜎-Field)										Never
Dual ideal
Filter				Never	Never				$\varnothing \not \in {\mathcal {F}}$
Prefilter (Filter base)				Never	Never				$\varnothing \not \in {\mathcal {F}}$
Filter subbase				Never	Never				$\varnothing \not \in {\mathcal {F}}$
Open Topology							(even arbitrary $\cup$ )			Never
Closed Topology						(even arbitrary $\cap$ )				Never
Is necessarily true of ${\mathcal {F}}\colon$ or, is ${\mathcal {F}}$ closed under:	directed downward	finite intersections	finite unions	relative complements	complements in $\Omega$	countable intersections	countable unions	contains $\Omega$	contains $\varnothing$	Finite Intersection Property
Additionally, a *semiring* is a $π$ -system where every complement $B\setminus A$ is equal to a finite disjoint union of sets in ${\mathcal {F}}.$ A *semialgebra* is a semiring where every complement $\Omega \setminus A$ is equal to a finite disjoint union of sets in ${\mathcal {F}}.$ $A,B,A_{1},A_{2},\ldots$ are arbitrary elements of ${\mathcal {F}}$ and it is assumed that ${\mathcal {F}}\neq \varnothing .$

Definition of a filter

There are two competing definitions of a "filter on a set," both of which require that a filter be a dual ideal.^[6] One definition defines "filter" as a synonym of "dual ideal" while the other defines "filter" to mean a dual ideal that is also proper.

Warning: It is recommended that readers always check how "filter" is defined when reading mathematical literature.

A dual ideal^[6] on a set $S$ is a non-empty subset $F$ of $\wp (S)$ with the following properties:

$F$ $F$ is closed under finite intersections: If $A,B\in F,$ $A,B\in F,$ then so is their intersection.
- This property implies that if $\varnothing \not \in F$ then $F$ has the finite intersection property.
$F$ $F$ is upward closed/isotone:^[7] If $A\in F$ $A\in F$ and $A\subseteq B,$ $A\subseteq B,$ then $B\in F,$ $B\in F,$ for all subsets $B\subseteq S.$ $B\subseteq S.$
- This property entails that $S\in F$ (since $F$ is a non-empty subset of $\wp (S)$ ).

Given a set $S,$ a canonical partial ordering $\,\subseteq \,$ can be defined on the powerset $\wp (S)$ by subset inclusion, turning $(\wp (S),\subseteq )$ into a lattice. A "dual ideal" is just a filter with respect to this partial ordering. Note that if $S=\varnothing$ then there is exactly one dual ideal on $S,$ which is $\wp (S)=\{\varnothing \}.$

A filter on a set may be thought of as representing a "collection of large subsets".^[8]

Filter definitions

The article uses the following definition of "filter on a set."

Definition as a dual ideal: A filter on a set $S$ is a dual ideal on $S.$ Equivalently, a filter on $S$ is just a filter with respect the canonical partial ordering $(\wp (S),\subseteq )$ described above.

The other definition of "filter on a set" is the original definition of a "filter" given by Henri Cartan, which required that a filter on a set be a dual ideal that does not contain the empty set:

Original/Alternative definition as a proper dual ideal: A filter^[6] on a set $S$ is a dual ideal on $S$ with the following additional property:

$F$ is proper^[9]/non-degenerate:^[10] The empty set is not in $F$ (i.e. $\varnothing \not \in F$ ).

Note: This article does not require that a filter be proper.

The only non-proper filter on $S$ is $\wp (S).$ Much mathematical literature, especially that related to Topology, defines "filter" to mean a non-degenerate dual ideal.

Filter bases, subbases, and comparison

Filter bases and subbases

A subset $B$ of $\wp (S)$ is called a prefilter, filter base, or filter basis if $B$ is non-empty and the intersection of any two members of $B$ is a superset of some member(s) of $B.$ If the empty set is not a member of $B,$ we say $B$ is a proper filter base.

Given a filter base $B,$ the filter generated or spanned by $B$ is defined as the minimum filter containing $B.$ It is the family of all those subsets of $S$ which are supersets of some member(s) of $B.$ Every filter is also a filter base, so the process of passing from filter base to filter may be viewed as a sort of completion.

For every subset $T$ of $\wp (S)$ there is a smallest (possibly non-proper) filter $F$ containing $T,$ called the filter generated or spanned by $T.$ Similarly as for a filter spanned by a filter base, a filter spanned by a subset $T$ is the minimum filter containing $T.$ It is constructed by taking all finite intersections of $T,$ which then form a filter base for $F.$ This filter is proper if and only if every finite intersection of elements of $T$ is non-empty, and in that case we say that $T$ is a filter subbase.

Finer/equivalent filter bases

If $B$ and $C$ are two filter bases on $S,$ one says $C$ is finer than $B$ (or that $C$ is a refinement of $B$ ) if for each $B_{0}\in B,$ there is a $C_{0}\in C$ such that $C_{0}\subseteq B_{0}.$ For filter bases $A,$ $B,$ and $C,$ if $A$ is finer than $B$ and $B$ is finer than $C$ then $A$ is finer than $C.$ Thus the refinement relation is a preorder on the set of filter bases, and the passage from filter base to filter is an instance of passing from a preordering to the associated partial ordering.

If also $B$ is finer than $C,$ one says that they are equivalent filter bases. If $B$ and $C$ are filter bases, then $C$ is finer than $B$ if and only if the filter spanned by $C$ contains the filter spanned by $B.$ Therefore, $B$ and $C$ are equivalent filter bases if and only if they generate the same filter.

Examples

A filter in a poset can be created using the Rasiowa–Sikorski lemma, which is often used in forcing. Other filters include club filters and generic filters.

The set $\{\{N,N+1,N+2,\dots \}:N\in \mathbb {N} \}$ is called a filter base of tails of the sequence of natural numbers $(1,2,3,\dots ).$ A filter base of tails can be made of any net $\left(x_{\alpha }\right)_{\alpha \in A}$ using the construction $\left\{\left\{x_{\alpha }:\alpha \in A,\alpha _{0}\leq \alpha \right\}:\alpha _{0}\in A\right\},$ where the filter that this filter base generates is called the net's eventuality filter. Therefore, all nets generate a filter base (and therefore a filter). Since all sequences are nets, this holds for sequences as well.

Let $S$ be a set and $C$ be a non-empty subset of $S.$ Then $\{C\}$ is a filter base. The filter it generates (that is, the collection of all subsets containing $C$ ) is called the principal filter generated by $C.$ A filter is said to be a free filter if the intersection of all of its members is empty. A proper principal filter is not free. Since the intersection of any finite number of members of a filter is also a member, no proper filter on a finite set is free, and indeed is the principal filter generated by the common intersection of all of its members. A nonprincipal filter on an infinite set is not necessarily free. The Fréchet filter on an infinite set $S$ is the set of all subsets of $S$ that have finite complement. A filter on $S$ is free if and only if it includes the Fréchet filter. More generally, if $(X,\mu )$ is a measure space for which $\mu (X)=\infty ,$ the collection of all $A\subseteq X$ such that $\mu (X\smallsetminus A)<\infty$ forms a filter. The Fréchet filter is the case where $X=S$ and $\mu$ is the counting measure.

Every uniform structure on a set $X$ is a filter on $X\times X.$

Filters in model theory

For every filter $F$ on a set $S$ the set function defined by $m(A)\quad ={\begin{cases}1&{\text{if }}A\in F\\0&{\text{if }}S\smallsetminus A\in F\\{\text{is undefined}}&{\text{otherwise}}\end{cases}}$ is finitely additive — a "measure" if that term is construed rather loosely. Therefore, the statement $\left\{\,x\in S:\varphi (x)\,\right\}\in F$ can be considered somewhat analogous to the statement that $\varphi$ holds "almost everywhere". That interpretation of membership in a filter is used (for motivation, although it is not needed for actual proofs) in the theory of ultraproducts in model theory, a branch of mathematical logic.

Filters in topology

In topology and analysis, filters are used to define convergence in a manner similar to the role of sequences in a metric space. Both nets and filters provide very general contexts to unify the various notions of limit to arbitrary topological spaces. A sequence is usually indexed by the natural numbers $\mathbb {N} ,$ which are a totally ordered set. Nets generalize the notion of a sequence by requiring the index set simply be a directed set. If working only with certain categories of topological spaces, such as first-countable spaces for instance, sequences suffice to characterize most topological properties, but this is not true in general. However, filters (as well as nets) do always suffice to characterize most topological properties. An advantage to using filters is that they do not involve any set other than $X$ (and its subsets) whereas sequences and nets rely on directed sets that may be unrelated to $X.$ Moreover, the set of all filters on $X$ is a set whereas the class of all nets valued in $X$ is not (it is a proper class).

Neighbourhood bases

Let ${\mathcal {N}}_{x}$ be the neighbourhood filter at point $x$ in a topological space $X.$ This means that ${\mathcal {N}}_{x}$ is the set of all topological neighbourhoods of the point $x.$ It can be verified that ${\mathcal {N}}_{x}$ is a filter. A neighbourhood system is another name for a neighbourhood filter. A family ${\mathcal {N}}$ of neighbourhoods of $x$ is a neighbourhood base at $x$ if ${\mathcal {N}}$ generates the filter ${\mathcal {N}}_{x}.$ This means that each subset $S$ of $X$ is a neighbourhood of $x$ if and only if there exists $N\in {\mathcal {N}}$ such that $N\subseteq S.$

Convergent filters and cluster points

We say that a filter base $B$ converges to a point $x,$ written $B\to x,$ if the neighbourhood filter ${\mathcal {N}}_{x}$ is contained in the filter $F$ generated by $B;$ that is, if $B$ is finer than ${\mathcal {N}}_{x}.$ In particular, a filter $F$ (which is a filter base that generates itself) converges to $x$ if ${\mathcal {N}}_{x}\subseteq F.$ Explicitly, to say that a filter base $B$ converges to $x$ means that for every neighbourhood $U$ of $x,$ there is a $B_{0}\in B$ such that $B_{0}\subseteq U.$ If a filter base $B$ converges to a point $x,$ then $x$ is called a limit (point) of $B$ and $B$ is called a convergent filter base.

A filter base $B$ on $X$ is said to cluster at $x$ (or have $x$ as a cluster point) if and only if each element of $B$ has non-empty intersection with each neighbourhood of $x.$ Every limit point is a cluster point but the converse is not true in general. However, every cluster point of an ultrafilter is a limit point.

By definition, every neighbourhood base ${\mathcal {N}}$ at a given point $x$ generates ${\mathcal {N}}_{x},$ so ${\mathcal {N}}$ converges to $x.$ If $C$ is a filter base on $X$ then $C\to x$ if $C$ is finer than any neighbourhood base at $x.$ For the neighborhood filter at that point, the converse holds as well: any basis of a convergent filter refines the neighborhood filter.

Notes

^ Cartan 1937a.
^ Cartan 1937b.
^ Igarashi, Ayumi; Zwicker, William S. (16 February 2021). "Fair division of graphs and of tangled cakes". arXiv:2102.08560 [math.CO].
^ Davey, B. A.; Priestley, H. A. (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press. p. 184.
^ ^a ^b Bergman & Hrushovski 1998.
^ ^a ^b ^c Dugundji 1966, pp. 211–213.
^ Dolecki & Mynard 2016, pp. 27–29.
^ Koutras et al. 2021.
^ Goldblatt, R. Lectures on the Hyperreals: an Introduction to Nonstandard Analysis. p. 32.
^ Narici & Beckenstein 2011, pp. 2–7.

References

Nicolas Bourbaki, General Topology (Topologie Générale), ISBN 0-387-19374-X (Ch. 1-4): Provides a good reference for filters in general topology (Chapter I) and for Cauchy filters in uniform spaces (Chapter II)
Bourbaki, Nicolas (1987) [1981]. Topological Vector Spaces: Chapters 1–5. Éléments de mathématique. Translated by Eggleston, H.G.; Madan, S. Berlin New York: Springer-Verlag. ISBN 3-540-13627-4. OCLC 17499190.
Burris, Stanley; Sankappanavar, Hanamantagouda P. (1981). A Course in Universal Algebra (PDF). Springer-Verlag. ISBN 3-540-90578-2. Archived from the original on 15 December 2021.
Burris, Stanley; Sankappanavar, Hanamantagouda P. (2012). A Course in Universal Algebra (PDF). Springer-Verlag. ISBN 978-0-9880552-0-9. Archived from the original on 1 April 2022.
Cartan, Henri (1937a). "Théorie des filtres". Comptes rendus hebdomadaires des séances de l'Académie des sciences. 205: 595–598.
Cartan, Henri (1937b). "Filtres et ultrafiltres". Comptes rendus hebdomadaires des séances de l'Académie des sciences. 205: 777–779.
Dolecki, Szymon; Mynard, Frédéric (2016). Convergence Foundations Of Topology. New Jersey: World Scientific Publishing Company. ISBN 978-981-4571-52-4. OCLC 945169917.
Dugundji, James (1966). Topology. Boston: Allyn and Bacon. ISBN 978-0-697-06889-7. OCLC 395340485.
Koutras, Costas D.; Moyzes, Christos; Nomikos, Christos; Tsaprounis, Konstantinos; Zikos, Yorgos (20 October 2021). "On Weak Filters and Ultrafilters: Set Theory From (and for) Knowledge Representation". Logic Journal of the IGPL. doi:10.1093/jigpal/jzab030.
MacIver R., David (1 July 2004). "Filters in Analysis and Topology" (PDF). Archived from the original (PDF) on 2007-10-09. (Provides an introductory review of filters in topology and in metric spaces.)
Narici, Lawrence; Beckenstein, Edward (2011). Topological Vector Spaces. Pure and applied mathematics (Second ed.). Boca Raton, FL: CRC Press. ISBN 978-1584888666. OCLC 144216834.
Willard, Stephen (1970). General Topology. Reading Massachusetts: Addison-Wesley Publishing Company. ISBN 9780201087079. (Provides an introductory review of filters in topology.)
Willard, Stephen (2004) [1970]. General Topology. Mineola, N.Y.: Dover Publications. ISBN 978-0-486-43479-7. OCLC 115240.
Wilansky, Albert (2013). Modern Methods in Topological Vector Spaces. Mineola, New York: Dover Publications, Inc. ISBN 978-0-486-49353-4. OCLC 849801114.