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 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 $X$ is a order filter on the power set of $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 $X$, a filter ${\mathcal {F}}$ on $X$ is a set of subsets of $X$ such that:

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

A proper (or non-degenerate) filter is a filter which is proper as a subset of the powerset ${\mathcal {P}}(X)$ (i.e., the only improper filter is ${\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. Many authors adopt the convention that a filter must be proper by definition.

Given two filters ${\mathcal {F}}$ and ${\mathcal {G}}$ on the same set, ${\mathcal {F}}$ is said to be coarser than ${\mathcal {G}}$ (or a subfilter of ${\mathcal {G}}$) and ${\mathcal {G}}$ is said to be finer than ${\mathcal {F}}$ (or subordinate to ${\mathcal {F}}$) when ${\mathcal {F}}\subseteq {\mathcal {G}}$.

Examples

• The singleton set ${\mathcal {F}}=\{X\}$ is called the trivial or indiscrete filter on $X$.
• If $Y$ is a subset of $X$, the subsets of $X$ which are supersets of $Y$ form a principal filter.
• If $X$ is a topological space and $x\in X$, then the set of neighborhoods of $x$ is a filter on $X$, the neighborhood filter of $x$.
• Many examples arise from various "largeness" conditions:
  • If $X$ is a set, the set of all cofinite subsets of $X$ (i.e., those sets whose complement in $X$ is finite) is a filter on $X$, the Fréchet filter.
  • Similarly, if $X$ is a set, the cocountable subsets of $X$ (those whose complement is countable) form a filter which is finer than the Fréchet filter. More generally, for any cardinal $\kappa$, the subsets whose complement has cardinal at most $\kappa$ form a filter.
  • If $X$ is a complete measure space (e.g., $\mathbb {R} ^{n}$ with the Lebesgue measure), the conull subsets of $X$, i.e., the subsets whose complement has measure zero, form a filter on $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 $X$ is a measure space, the subsets whose complement is contained in a measurable subset of finite measure form a filter on $X$.
  • If $X$ is a topological space, the comeager subsets of $X$, i.e., those whose complement is meager, form a filter on $X$.
  • The subsets of $\mathbb {N}$ which have a natural density of 1 form a filter on $\mathbb {N}$.
• The club filter of a regular uncountable cardinal $\kappa$ is the filter of all sets containing a club subset of $\kappa$.
• If $({\mathcal {F}}_{i})_{i\in I}$ is a family of filters on $X$ and ${\mathcal {J}}$ is a filter on $I$ then $\bigcup _{A\in {\mathcal {J}}}\bigcap _{i\in A}{\mathcal {F}}_{i}$ is a filter on $X$ called Kowalsky's filter.

Principal and free filters

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

A principal filter on $X$ is a filter ${\mathcal {F}}$ which has a particularly simple form: it contains exactly the supersets of $Y$, for some fixed subset $Y\subseteq X$. When $Y=\varnothing$, this yields the improper filter. In the particular case where $Y$ is a singleton, the filter is said to be discrete, i.e., a discrete filter on $X$ is the set of subsets of $X$ which contain $y$, for some fixed element $y\in X$ (the filter is also said to be "principal at $y$").

A filter ${\mathcal {F}}$ is principal if and only if the kernel of ${\mathcal {F}}$ is an element of ${\mathcal {F}}$, and when this is the case, ${\mathcal {F}}$ consists of the supersets of its kernel. 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 $x$ is an element of the kernel, it is fixed by $x$). A filter on a set $X$ is free if and only if it contains the Fréchet filter on $X$.

For every filter ${\mathcal {F}}$ on $X$, there exists a unique pair of filters ${\mathcal {F}}_{f}$ (the free part of ${\mathcal {F}}$) and ${\mathcal {F}}_{p}$ (the principal part of ${\mathcal {F}}$) on $X$ such that ${\mathcal {F}}_{f}$ is free, ${\mathcal {F}}_{p}$ is principal, and ${\mathcal {F}}_{f}\cap {\mathcal {F}}_{p}={\mathcal {F}},$, and ${\mathcal {F}}_{p}$ and ${\mathcal {F}}_{f}$ do not mesh (defined below).

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

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 $P$ is a subset $F$ of $P$ which is upwards-closed (if $x\in F$ and $x\leq y$ then $y\in F$) and downwards-directed (every finite subset of $F$ has a lower bound in $F$). A filter on a set $X$ is the same as a filter on the powerset ${\mathcal {P}}(X)$ ordered by inclusion.

Constructions of filters

Intersection of filters

If $({\mathcal {F}}_{i})_{i\in I}$ is a family of filters on $X$, its intersection $\bigcap _{i\in I}{\mathcal {F}}_{i}$ is a filter on $X$. It consists of the subsets which can be written as $\bigcup _{i\in I}A_{i}$ where $A_{i}\in {\mathcal {F}}_{i}$ for each $i\in I$.

The intersection is a greatest lower bound operation in the set of filters on $X$ partially ordered by inclusion. This endows the filters on $X$ with a complete lattice structure.

Filter generated by a family of subsets

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

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

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

Two filters ${\mathcal {F}}$ and ${\mathcal {G}}$ on $X$ mesh when $\langle {\mathcal {F}}\cup {\mathcal {G}}\rangle$ is proper.

Filter bases

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

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

Examples

• When $X$ is a topological space and $x\in X$, a filter base of the neighborhood filter of $x$ is known as a neighborhood base for $x$, and similarly, a filter subbase of the neighborhood filter of $x$ is known as a neighborhood subbase for $x$. The open neighborhoods of $x$ always form a neighborhood base for $x$, by definition of the neighborhood filter. In $X=\mathbb {R} ^{n}$, the closed balls of positive radius around $x$ also form a neighborhood base for $x$.
• Let $X$ be an infinite set and let ${\mathcal {F}}$ consist of the subsets of $X$ which contain all points but one. Then ${\mathcal {F}}$ is a filter subbase of the Fréchet filter on $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 ${\mathcal {F}}$, such as the one formed by the subsets of $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 $X$ is a topological space, the dense open subsets of $X$ form a filter base on $X$, because they are closed under finite intersection. The filter they generate consists of the complements of nowhere dense subsets. On $X=\mathbb {R} ^{n}$, restricting to the null dense open subsets yields another filter base for the same filter.
• Similarly, if $X$ is a topological space, the countable intersections of dense open subsets form a filter base which generates the filter of comeager subsets.
• Let $X$ be a set and let $(x_{i})_{i\in I}$ be a net with values in $X$, i.e., a family whose domain $I$ is a directed set. The filter base of tails of $(x_{i})$ consists of the sets $\{x_{j},j\geq i\}$ for $i\in I$; it is downwards-closed by directedness of $I$. An elementary filter is a filter which has a filter base of this form. This example is fundamental in the application of filters in topology.
• Every π-system is a filter base.

Trace of a filter on a subset

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

Image or preimage of a filter by a function

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

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

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

If ${\mathcal {F}}$ is a filter on $X$ and $f$ is additionally surjective, then $f({\mathcal {F}})$ is a filter on $Y$; furthermore, if ${\mathcal {B}}$ is a filter base of ${\mathcal {F}}$ then $f({\mathcal {B}})$ is a filter base of $f({\mathcal {F}})$. The kernels of ${\mathcal {F}}$ and $f({\mathcal {F}})$ are linked by $f\left(\bigcap {\mathcal {F}}\right)\subseteq \bigcap f({\mathcal {F}})$.

Similarly, when ${\mathcal {F}}$ is a family of subsets of $Y$, its preimage by $f$ is defined as

$$f^{-1}({\mathcal {F}})=\{\{x\in X\mid f(x)\in A\},A\in {\mathcal {F}}\}$$

If ${\mathcal {F}}$ is a filter on $Y$ and $f$ is additionally injective, then $f^{-1}({\mathcal {F}})$ is a filter on $X$ (since it is isomorphic to the trace of ${\mathcal {F}}$ on the image of $f$); furthermore, if ${\mathcal {B}}$ is a filter base of ${\mathcal {F}}$ then $f^{-1}({\mathcal {B}})$ is a filter base of $f^{-1}({\mathcal {F}})$, and unlike the image case, it also holds that if ${\mathcal {S}}$ is a filter subbase of ${\mathcal {F}}$ then $f^{-1}({\mathcal {S}})$ is a filter subbase of $f^{-1}({\mathcal {F}})$. The kernels are linked by $f^{-1}\left(\bigcap {\mathcal {F}}\right)=\bigcap f^{-1}({\mathcal {F}})$.

Product of filters

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

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

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

References

• Adams, Colin; Franzosa, Robert (2009). Introduction to Topology: Pure and Applied. New Delhi: Pearson Education. ISBN 978-81-317-2692-1. OCLC 789880519.
• Arkhangel'skii, Alexander Vladimirovich; Ponomarev, V.I. (1984). Fundamentals of General Topology: Problems and Exercises. Mathematics and Its Applications. Vol. 13. Dordrecht Boston: D. Reidel. ISBN 978-90-277-1355-1. OCLC 9944489.
• Berberian, Sterling K. (1974). Lectures in Functional Analysis and Operator Theory. Graduate Texts in Mathematics. Vol. 15. New York: Springer. ISBN 978-0-387-90081-0. OCLC 878109401.
• Bourbaki, Nicolas (1989) [1966]. General Topology: Chapters 1–4 [Topologie Générale]. Éléments de mathématique. Berlin New York: Springer Science & Business Media. ISBN 978-3-540-64241-1. OCLC 18588129.
• Bourbaki, Nicolas (1989) [1967]. General Topology 2: Chapters 5–10 [Topologie Générale]. Éléments de mathématique. Vol. 4. Berlin New York: Springer Science & Business Media. ISBN 978-3-540-64563-4. OCLC 246032063.
• 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. (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.
• Comfort, William Wistar; Negrepontis, Stylianos (1974). The Theory of Ultrafilters. Vol. 211. Berlin Heidelberg New York: Springer-Verlag. ISBN 978-0-387-06604-2. OCLC 1205452.
• Császár, Ákos (1978). General topology. Translated by Császár, Klára. Bristol England: Adam Hilger Ltd. ISBN 0-85274-275-4. OCLC 4146011.
• Dixmier, Jacques (1984). General Topology. Undergraduate Texts in Mathematics. Translated by Berberian, S. K. New York: Springer-Verlag. ISBN 978-0-387-90972-1. OCLC 10277303.
• 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.
• Dunford, Nelson; Schwartz, Jacob T. (1988). Linear Operators. Pure and applied mathematics. Vol. 1. New York: Wiley-Interscience. ISBN 978-0-471-60848-6. OCLC 18412261.
• Edwards, Robert E. (1995). Functional Analysis: Theory and Applications. New York: Dover Publications. ISBN 978-0-486-68143-6. OCLC 30593138.
• Howes, Norman R. (23 June 1995). Modern Analysis and Topology. Graduate Texts in Mathematics. New York: Springer-Verlag Science & Business Media. ISBN 978-0-387-97986-1. OCLC 31969970. OL 1272666M.
• Jarchow, Hans (1981). Locally convex spaces. Stuttgart: B.G. Teubner. ISBN 978-3-519-02224-4. OCLC 8210342.
• Jech, Thomas (2006). Set Theory: The Third Millennium Edition, Revised and Expanded. Berlin New York: Springer Science & Business Media. ISBN 978-3-540-44085-7. OCLC 50422939.
• Joshi, K. D. (1983). Introduction to General Topology. New York: John Wiley and Sons Ltd. ISBN 978-0-85226-444-7. OCLC 9218750.
• Kelley, John L. (1975) [1955]. General Topology. Graduate Texts in Mathematics. Vol. 27 (2nd ed.). New York: Springer-Verlag. ISBN 978-0-387-90125-1. OCLC 1365153.
• Köthe, Gottfried (1983) [1969]. Topological Vector Spaces I. Grundlehren der mathematischen Wissenschaften. Vol. 159. Translated by Garling, D.J.H. New York: Springer Science & Business Media. ISBN 978-3-642-64988-2. MR 0248498. OCLC 840293704.
• 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. 31: 68–95. 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.
• Robertson, Alex P.; Robertson, Wendy J. (1980). Topological Vector Spaces. Cambridge Tracts in Mathematics. Vol. 53. Cambridge England: Cambridge University Press. ISBN 978-0-521-29882-7. OCLC 589250.
• Schaefer, Helmut H.; Wolff, Manfred P. (1999). Topological Vector Spaces. GTM. Vol. 8 (Second ed.). New York, NY: Springer New York Imprint Springer. ISBN 978-1-4612-7155-0. OCLC 840278135.
• Schechter, Eric (1996). Handbook of Analysis and Its Foundations. San Diego, CA: Academic Press. ISBN 978-0-12-622760-4. OCLC 175294365.
• Schubert, Horst (1968). Topology. London: Macdonald & Co. ISBN 978-0-356-02077-8. OCLC 463753.
• Trèves, François (2006) [1967]. Topological Vector Spaces, Distributions and Kernels. Mineola, N.Y.: Dover Publications. ISBN 978-0-486-45352-1. OCLC 853623322.
• Wilansky, Albert (2013). Modern Methods in Topological Vector Spaces. Mineola, New York: Dover Publications, Inc. ISBN 978-0-486-49353-4. OCLC 849801114.
• Wilansky, Albert (17 October 2008) [1970]. Topology for Analysis. Mineola, New York: Dover Publications, Inc. ISBN 978-0-486-46903-4. OCLC 227923899.
• Willard, Stephen (2004) [1970]. General Topology. Mineola, N.Y.: Dover Publications. ISBN 978-0-486-43479-7. OCLC 115240.

Families ${\mathcal {F}}$ of sets over $\Omega$
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
Filter
Proper filter				Never	Never				Never
Prefilter (Filter base)
Filter subbase
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 .$