Filter (mathematics)

File:Filter vs ultrafilter.svg

The power set lattice of the set Template:Brace, with upper set ↑Template:Brace colored dark green. This upper set is a Template:Em, and even a Template:Em. It is not an Template:Em, because including also the light green elements extends it to the larger nontrivial filter ↑Template:Brace. Since the latter cannot be extended further, ↑Template:Brace is an ultrafilter.

In mathematics, a filter or order filter is a special subset of a partially ordered set (poset), describing "large" or "eventual" elements. Filters appear in order and lattice theory, but also topology, whence they originate. The notion dual to a filter is an order ideal.

Special cases of filters include ultrafilters, which are filters that cannot be enlarged, and describe nonconstructive techniques in mathematical logic.

Filters on sets were introduced by Henri Cartan in 1937. Nicolas Bourbaki, in their book Topologie Générale, popularized filters as an alternative to E. H. Moore and Herman L. Smith's 1922 notion of a net; order filters generalize this notion from the specific case of a power set under inclusion to arbitrary partially ordered sets. Nevertheless, the theory of power-set filters retains interest in its own right, in part for substantial applications in topology.

Motivation

Fix a partially ordered set (poset) Template:Mvar. Intuitively, a filter Template:Mvar is a subset of Template:Mvar whose members are elements large enough to satisfy some criterion.Template:Sfn For instance, if x ∈ P, then the set of elements above Template:Mvar is a filter, called the principal filter at Template:Mvar. (If Template:Mvar and Template:Mvar are incomparable elements of Template:Mvar, then neither the principal filter at Template:Mvar nor Template:Mvar is contained in the other.)

Similarly, a filter on a set Template:Mvar contains those subsets that are sufficiently large to contain some given Template:Em. For example, if Template:Mvar is the real line and x ∈ S, then the family of sets including Template:Mvar in their interior is a filter, called the neighborhood filter at Template:Mvar. The Template:Em in this case is slightly larger than Template:Mvar, but it still does not contain any other specific point of the line.

The above considerations motivate the upward closure requirement in the definition below: "large enough" objects can always be made larger.

To understand the other two conditions, reverse the roles and instead consider Template:Mvar as a "locating scheme" to find Template:Mvar. In this interpretation, one searches in some space Template:Mvar, and expects Template:Mvar to describe those subsets of Template:Mvar that contain the goal. The goal must be located somewhere; thus the empty set ∅ can never be in Template:Mvar. And if two subsets both contain the goal, then should "zoom in" to their common region.

An ultrafilter describes a "perfect locating scheme" where each scheme component gives new information (either "look here" or "look elsewhere"). Compactness is the property that "every search is fruitful," or, to put it another way, "every locating scheme ends in a search result."

A common use for a filter is to define properties that are satisfied by "generic" elements of some topological space. This application generalizes the "locating scheme" to find points that might be hard to write down explicitly.

Definition

A subset Template:Mvar of a partially ordered set (P, ≤) is a filter or dual ideal if the following are satisfied:

Downward directedness

Every finite subset of Template:Mvar has a lower bound. In other words, Template:Mvar is non-empty and for every x, y ∈ F there is some z ∈ F such that z ≤ x and z ≤ y.

Upward closure

For every x ∈ F and p ∈ P, the condition x ≤ p implies p ∈ F.

If, additionally, F ≠ P, then Template:Mvar is said to be a proper filter. Authors in set theory and mathematical logic often require all filters to be proper;Template:Sfn this article will eschew that convention. An ultrafilter is a proper filter contained in no other proper filter except itself.

Filter bases

A subset Template:Mvar of Template:Mvar is a base or basis for Template:Mvar if the upwards closure of Template:Mvar (i.e., the smallest upwards-closed set containing Template:Mvar) is equal to Template:Mvar. Since every filter is upwards-closed, every filter is a base for itself.

Moreover, if B ⊆ P is downward directed, then Template:Mvar generates an upper set Template:Mvar that is a filter (for which Template:Mvar is a base). Such sets are called prefilters, as well as the aforementioned filter base/basis, and Template:Mvar is said to be generated or spanned by Template:Mvar. A prefilter is proper if and only if it generates a proper filter.

Given p ∈ P, the set Template:Brace is the smallest filter containing p, and sometimes written ↑ p. Such a filter is called a principal filter; p is said to be the principal element of Template:Mvar, or generate Template:Mvar.

Refinement

Suppose Template:Mvar and Template:Mvar are two prefilters on Template:Mvar, and, for each Template:Mvar, there is a b ∈ B, such that b ≤ c. Then we say that Template:Mvar is Template:Visible anchor than (or refines) Template:Mvar; likewise, Template:Mvar is coarser than (or coarsens) Template:Mvar. Refinement is a preorder on the set of prefilters. In fact, if Template:Mvar also refines Template:Mvar, then Template:Mvar and Template:Mvar are called equivalent, for they generate the same filter. Thus passage from prefilter to filter is an instance of passing from a preordering to associated partial ordering.

Special cases

Historically, filters generalized to order-theoretic lattices before arbitrary partial orders. In the case of lattices, downward direction can be written as closure under finite meets: for all x, y ∈ F, one has x ∧ y ∈ F.

Linear filters

A linear (ultra)filter is an (ultra)filter on the lattice of vector subspaces of a given vector space, ordered by inclusion. Explicitly, a linear filter on a vector space Template:Mvar is a family Template:Mathcal of vector subspaces of Template:Mvar such that if A, B ∈ Template:Mathcal and Template:Mvar is a vector subspace of Template:Mvar that contains Template:Mvar, then A ∩ B ∈ Template:Mathcal and C ∈ Template:Mathcal.Template:Sfn

A linear filter is proper if it does not contain Template:Brace.Template:Sfn

Filters on a set; subbases

Given a set Template:Mvar, the power set Template:Mathcal(S) is partially ordered by set inclusion; filters on this poset are often just called "filters on Template:Mvar," in an abuse of terminology. For such posets, downward direction and upward closure reduce to:Template:Sfn

Closure under finite intersections

If A, B ∈ F, then so too is A ∩ B ∈ F.

Isotony

Template:Sfn If A ∈ F and A ⊆ B ⊆ S, then B ∈ F.

A proper or non-degenerateTemplate:Sfn filter is one that does not contain ∅, and these three conditions (including non-degeneracy) are Henri Cartan's original definition of a filter.Template:SfnTemplate:Sfn It is common, though not universal, to require filters on sets to be proper (whatever one's stance on poset filters); we shall again eschew this convention.

Prefilters on a set are proper if and only if they do not contain ∅ either.

For every subset Template:Mvar of Template:Mathcal(S), there is a smallest filter Template:Mvar containing Template:Mvar. As with prefilters, Template:Mvar is said to generate or span Template:Mvar; a base for Template:Mvar is the set Template:Mvar of all finite intersections of Template:Mvar. The set Template:Mvar is said to be a filter subbase when Template:Mvar (and thus Template:Mvar) is proper.

Proper filters on sets have the finite intersection property.

If $S=\varnothing$, then $S$ admits only the improper filter $\{\varnothing \}$.

Free filters

A filter is said to be a free filter if the intersection 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. But a nonprincipal filter on an infinite set is not necessarily free: a filter is free if and only if it includes the Fréchet filter (see Template:Slink).

Examples

See the image at the top of this article for a simple example of filters on the finite poset Template:Mathcal({1, 2, 3, 4}).

Partially order Template:Mathbb → Template:Mathbb, the space of real-valued functions on Template:Mathbb, by pointwise comparison. Then the set of functions "large at infinity,"$$\{f:\underset{x\to \pm \mathrm{\infty }}{\lim }f(x)=\mathrm{\infty }\}\text{,}$$is a filter on Template:Mathbb → Template:Mathbb. One can generalize this construction quite far by compactifying the domain and completing the codomain: if Template:Mvar is a set with distinguished subset Template:Mvar and Template:Mvar is a poset with distinguished element Template:Mvar, then Template:Brace is a filter in X → Y.

The set Template:Brace is a filter in Template:Mathcal(Template:Mathbb). More generally, if Template:Mvar is any directed set, then$$\{\{k:k\ge N\}:N\in D\}$$is a filter in Template:Mathcal(D), called the tail filter. Likewise any net Template:Brace_α∈Α generates the eventuality filter Template:Brace. A tail filter is the eventuality filter for x_α = α.

The Fréchet filter on an infinite set Template:Mvar is$$\{A:X\setminus A\text{ finite}\}\text{.}$$If (X, μ) is a measure space, then the collection Template:Brace is a filter. If μ(X) = ∞, then Template:Brace is also a filter; the Fréchet filter is the case where μ is counting measure.

Given an ordinal Template:Mvar with uncountable cofinality, a subset of Template:Mvar is called a club if it is closed in the order topology of Template:Mvar but has net-theoretic limit Template:Mvar. The clubs of Template:Mvar, and their supersets, form a filter: the club filter, ♣(a).

The previous construction generalizes as follows: any club Template:Mvar is also a collection of dense subsets (in the ordinal topology) of Template:Mvar, and ♣(a) meets each element of Template:Mvar. Replacing Template:Mvar with an arbitrary collection Template:Mvar of dense sets, there "typically" exists a filter meeting each element of Template:Mvar, called a generic filter. For countable Template:Mvar, the Rasiowa–Sikorski lemma implies that such a filter must exist; for "small" uncountable Template:Mvar, the existence of such a filter can be forced through Martin's axiom.

Let P denote the set of partial orders of limited cardinality, modulo isomorphism. Partially order Template:Mvar by:

A ≤ B if there exists a strictly increasing f : A → B.

Then the subset of non-atomic partial orders forms a filter. Likewise, if Template:Mvar is the set of injective modules over some given commutative ring, of limited cardinality, modulo isomorphism, then a partial order on Template:Mvar is:

A ≤ B if there exists an injective linear map f : A → B.

Given any infinite cardinal κ, the modules in Template:Mvar that cannot be generated by fewer than κ elements form a filter.

Every uniform structure on a set Template:Mvar is a filter on X × X.

Relationship to ideals

The dual notion to a filter — that is, the concept obtained by reversing all ≤ and exchanging ∧ with ∨ — is an order ideal. Because of this duality, any question of filters can be mechanically translated to a question about ideals and vice versa; in particular, a prime or maximal filter is a filter whose corresponding ideal is (respectively) prime or maximal.

A filter is an ultrafilter if and only if the corresponding ideal is minimal.

In model theory

For every filter Template:Mvar on a set Template:Mvar, the set function defined by$$m(A)=\{\begin{array}{ll}1& \text{if }A\in F\\ 0& \text{if }S\setminus A\in F\\ \text{is undefined}& \text{otherwise}\end{array}$$is finitely additive — a "measure," if that term is construed rather loosely. Moreover, the measures so constructed are defined everywhere if Template:Mvar is an ultrafilter. Therefore, the statement$$\{x\in S:\phi (x)\}\in F$$can be considered somewhat analogous to the statement that φ holds "almost everywhere." That interpretation of membership in a filter is used (for motivation, not actual Template:Em) in the theory of ultraproducts in model theory, a branch of mathematical logic.

In topology

In general topology and analysis, filters are used to define convergence in a manner similar to the role of sequences in a metric space. They unify the concept of a limit across the wide variety of arbitrary topological spaces.

To understand the need for filters, begin with the equivalent concept of a net. A sequence is usually indexed by the natural numbers Template:Mathbb, which are a totally ordered set. Nets generalize the notion of a sequence by replacing Template:Mathbb with an arbitrary directed set. In certain categories of topological spaces, such as first-countable spaces, sequences characterize most topological properties, but this is not true in general. However, nets — as well as filters — always do characterize those topological properties.

Filters do not involve any set external to the topological space Template:Mvar, whereas sequences and nets rely on other directed sets. For this reason, the collection of all filters on Template:Mvar is always a set, whereas the collection of all Template:Mvar-valued nets is a proper class.

Neighborhood bases

Any point Template:Mvar in the topological space Template:Mvar defines a neighborhood filter or system Template:Mathcal_x: namely, the family of all sets containing Template:Mvar in their interior. A set Template:Mathcal of neighborhoods of Template:Mvar is a neighborhood base at Template:Mvar if Template:Mathcal generates Template:Mathcal_x. Equivalently, S ⊆ X is a neighborhood of Template:Mvar if and only if there exists N ∈ Template:Mathcal such that N ⊆ S.

Convergent filters and cluster points

A prefilter Template:Mvar converges to a point Template:Mvar, written B → x, if and only if Template:Mvar generates a filter Template:Mvar that contains the neighborhood filter Template:Mathcal_x — explicitly, for every neighborhood Template:Mvar of Template:Mvar, there is some V ∈ B such that V ⊆ U. Less explicitly, B → x if and only if Template:Mvar refines Template:Mathcal_x, and any neighborhood base at Template:Mvar can replace Template:Mathcal_x in this condition. Clearly, every neighborhood base at Template:Mvar converges to Template:Mvar.

A filter Template:Mvar (which generates itself) converges to Template:Mvar if Template:Mathcal_x ⊆ F. The above can also be reversed to characterize the neighborhood filter Template:Mathcal_x: Template:Mathcal_x is the finest filter coarser than each filter converging to Template:Mvar.

If B → x, then Template:Mvar is called a limit (point) of Template:Mvar. The prefilter Template:Mvar is said to cluster at Template:Mvar (or have Template:Mvar as a cluster point) if and only if each element of Template:Mvar has non-empty intersection with each neighborhood of Template:Mvar. Every limit point is a cluster point but the converse is not true in general. However, every cluster point of an Template:Emfilter is a limit point.

See also

• Template:Annotated link
• Template:Annotated link
• Template:Annotated link
• Template:Annotated link
• Template:Annotated link

References

• Nicolas Bourbaki, General Topology (Topologie Générale), Template:ISBN (Ch. 1–4): Provides a good reference for filters in general topology (Chapter I) and for Cauchy filters in uniform spaces (Chapter II)
• Template:Bourbaki Topological Vector Spaces Part 1 Chapters 1–5
• Template:Dolecki Mynard Convergence Foundations Of Topology
• Template:Dugundji Topology
• (Provides an introductory review of filters in topology and in metric spaces.)
• Template:Narici Beckenstein Topological Vector Spaces
• Template:Willard General Topology
• Template:Wilansky Modern Methods in Topological Vector Spaces