# Filter (mathematics)

In mathematics, a **filter** is a special subset of a partially ordered set. For example, the power set of some set, partially ordered by set inclusion, is a filter. Filters appear in order and lattice theory, but can also be found in topology whence they originate. The dual notion of a filter is an ideal.

Filters were introduced by Henri Cartan in 1937^{[1]}^{[2]} and subsequently used by Bourbaki in their book *Topologie Générale* as an alternative to the similar notion of a net developed in 1922 by E. H. Moore and H. L. Smith.

## Motivation

Intuitively, a filter on a partially ordered set (*poset*) contains those elements that are large enough to satisfy some 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*. (Notice that 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.)

Similarly, a filter on a set contains those subsets that are sufficiently large to contain *something*. For example, if the set is the real line and *x* is one of its points, then the family of sets that contain *x* in their interior is a filter, called the **filter of neighbourhoods** of *x*. (Notice that the *thing* in this case is slightly larger than *x*, but it still doesn't contain any other specific point of the line.)

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.

## General definition

A subset *F* of a partially ordered set (*P*,≤) is a **filter** if the following conditions hold:

- For every
*x*,*y*in*F*, there is some element*z*in*F*such that*z*≤*x*and*z*≤*y*. (*F*is a**filter base**, or downward directed) - For every
*x*in*F*and*y*in*P*,*x*≤*y*implies that*y*is in*F*. (*F*is an*upper set*, or upward closed)

A filter is **proper** if it is not equal to the whole set *P*. This condition is sometimes added to the definition of a 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*,≤) is a filter, if and only if it is an upper set that is closed under finite intersection (infima or meet), i.e., for all *x*, *y* in *F*, we find that *x* ∧ *y* is also in *F*.

The smallest filter that contains a given element *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* ≤ *x*} and is denoted by prefixing *p* with an upward arrow: .

The dual notion of a filter, i.e. the concept obtained by reversing all ≤ and exchanging ∧ with ∨, 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.

## Filter on a set

A special case of a filter is a filter defined on a set. Given a set *S*, a partial ordering ⊆ can be defined on the powerset **P**(*S*) by subset inclusion, turning (**P**(*S*),⊆) into a lattice. Define a **filter** *F* on *S* as a nonempty subset of **P**(*S*) with the following properties:

*S*is in*F*, and if*A*and*B*are in*F*, then so is their intersection. (*F is closed under finite intersection*)- The empty set is not in
*F*. (*F is a proper filter*) - If
*A*is in*F*and*A*is a subset of*B*, then*B*is in*F*, for all subsets*B*of*S*. (*F is upward closed*)

The first two properties imply that a **filter on a set** has the finite intersection property. Note that with this definition, a filter on a set is indeed a filter; in fact, it is a proper filter. Because of this, sometimes this is called a **proper filter on a set**; however, the adjective "proper" is generally omitted and considered implicit. The only nonproper filter on *S* is **P**(*S*).

A **filter base** (or **filter basis**) is a subset *B* of **P**(*S*) with the following properties:

*B*is non-empty and the intersection of any two sets of*B*contains a set of*B*. (*B is downward directed*)- The empty set is not in
*B*. (*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 the subsets of *S* which contain some set 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.

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} ∈ *B*, there is a *C*_{0} ∈ *C* such that *C*_{0} ⊆ *B*_{0}. 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. - 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.

For any subset *T* of **P**(*S*) there is a smallest (possibly nonproper) filter *F* containing *T*, called the filter generated or spanned by *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 any finite intersection of elements of *T* is non-empty, and in that case we say that *T* is a **filter subbase**.

### Examples

- Let
*S*be a nonempty set and*C*be a nonempty subset. Then is a filter base. The filter it generates (i.e., 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 principal filter is not free. Since the intersection of any finite number of members of a filter is also a member, no 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 contains the Fréchet filter.

- Every uniform structure on a set
*X*is a filter on*X*×*X*.

- A filter in a poset can be created using the Rasiowa-Sikorski lemma, often used in forcing.

- The set is called a
*filter base of tails*of the sequence of natural numbers . A filter base of tails can be made of any net using the construction . Therefore, all nets generate a filter base (and therefore a filter). Since all sequences are nets, this holds for sequences as well.

### Filters in model theory

For any filter *F* on a set *S*, the set function defined by

is finitely additive — a "measure" if that term is construed rather loosely. Therefore the statement

can be considered somewhat analogous to the statement that φ 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.

In topology and related areas of mathematics, a filter is a generalization of a net. 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, which are a totally ordered set. Thus, limits in first-countable spaces can be described by sequences. However, if the space is not first-countable, nets or filters must be used. Nets generalize the notion of a sequence by requiring the index set simply be a directed set. Filters can be thought of as sets built from multiple nets. Therefore, both the limit of a filter and the limit of a net are conceptually the same as the limit of a sequence.

#### Neighbourhood bases

Let *X* be a topological space and *x* a point of *X*.

- Take
*N*_{x}to be the**neighbourhood filter**at point*x*for*X*. This means that*N*_{x}is the set of all topological neighbourhoods of the point*x*. It can be verified that*N*_{x}is a filter. A**neighbourhood system**is another name for a**neighbourhood filter**.

- To say that
*N*is a**neighbourhood base**at*x*for*X*means that each subset*V*_{0}of X is a neighbourhood of*x*if and only if there exists*N*_{0}∈*N*such that*N*_{0}⊆*V*_{0}. Note that every neighbourhood base at*x*is a filter base that generates the neighbourhood filter at*x*.

#### Convergent filter bases

Let *X* be a topological space and *x* a point of *X*.

- To say that a filter base
*B***converges**to*x*, denoted*B*→*x*, means that for every neighbourhood*U*of*x*, there is a*B*_{0}∈*B*such that*B*_{0}⊆*U*. In this case,*x*is called a limit of*B*and*B*is called a**convergent filter base**.

- Every neighbourhood base
*N*of*x*converges to*x*.- If
*N*is a neighbourhood base at*x*and*C*is a filter base on*X*, then*C*→*x*if and only if*C*is finer than*N*. - If
*Y*⊆*X*, a point*p ∈ X*is called a**limit point**of*Y*in*X*if and only if each neighborhood*U*of*p*in*X*intersects*Y*. This happens if and only if there is a filter base of subsets of*Y*that converges to*p*in*X*.

- If
- For
*Y*⊆*X*, the following are equivalent:- (i) There exists a filter base
*F*whose elements are all contained in*Y*such that*F*→*x*. - (ii) There exists a filter
*F*such that*Y*is an element of*F*and*F*→*x*. - (iii) The point
*x*lies in the closure of*Y*.

- (i) There exists a filter base

Indeed:

(i) implies (ii): if *F* is a filter base satisfying the properties of (i), then the filter associated to *F* satisfies the properties of (ii).

(ii) implies (iii): if *U* is any open neighborhood of *x* then by the definition of convergence *U* contains an element of *F*; since also *Y* is an element of *F*,
*U* and *Y* have nonempty intersection.

(iii) implies (i): Define . Then *F* is a filter base satisfying the properties of (i).

#### Clustering

Let *X* be a topological space and *x* a point of *X*.

- 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 nonempty intersection with each neighbourhood of*x*.- If a filter base
*B*clusters at*x*and is finer than a filter base*C*, then*C*clusters at*x*too. - Every limit of a filter base is also a cluster point of the base.
- A filter base
*B*that has*x*as a cluster point may not converge to*x*. But there is a finer filter base that does. For example the filter base of finite intersections of sets of the subbase . - For a filter base
*B*, the set ∩{cl(*B*_{0}) :*B*_{0}∈*B*} is the set of all cluster points of*B*(note: cl(*B*_{0}) is the closure of*B*_{0}). Assume that*X*is a complete lattice.- The limit inferior of
*B*is the infimum of the set of all cluster points of*B*. - The limit superior of
*B*is the supremum of the set of all cluster points of*B*. *B*is a convergent filter base if and only if its limit inferior and limit superior agree; in this case, the value on which they agree is the limit of the filter base.

- The limit inferior of

- If a filter base

#### Properties of a topological space

Let *X* be a topological space.

*X*is a Hausdorff space if and only if every filter base on*X*has at most one limit.*X*is compact if and only if every filter base on*X*clusters.*X*is compact if and only if every filter base on*X*is a subset of a convergent filter base.*X*is compact if and only if every ultrafilter on*X*converges.

#### Functions on topological spaces

Let , be topological spaces. Let be a filter base on and be a function. The image of under is is the set . The image forms a filter base on . (Do not confuse the x element of B and x point in X!)

- is continuous at if and only if implies .

#### Cauchy filters

Let be a metric space.

- To say that a filter base
*B*on*X*is**Cauchy**means that for each real number ε>0, there is a*B*_{0}∈*B*such that the metric diameter of*B*_{0}is less than ε. - Take (
*x*) to be a sequence in metric space_{n}*X*. (*x*) is a Cauchy sequence if and only if the filter base {{_{n}*x*+1,...} :_{N},x_{N}*N*∈ {1,2,3,...} } is Cauchy.

More generally, given a uniform space *X*, a filter *F* on *X* is called **Cauchy filter** if for every entourage *U* there is an *A* ∈ *F* with (*x,y*) ∈ *U* for all *x,y* ∈ *A*. In a metric space this agrees with the previous definition. *X* is said to be complete if every Cauchy filter converges. Conversely, on a uniform space every convergent filter is a Cauchy filter. Moreover, every cluster point of a Cauchy filter is a limit point.

A compact uniform space is complete: on a compact space each filter has a cluster point, and if the filter is Cauchy, such a cluster point is a limit point. Further, a uniformity is compact if and only if it is complete and totally bounded.

Most generally, a Cauchy space is a set equipped with a class of filters declared to be Cauchy. These are required to have the following properties:

- for each
*x*in*X*, the ultrafilter at*x*,*U*(*x*), is Cauchy. - if
*F*is a Cauchy filter, and*F*is a subset of a filter*G*, then*G*is Cauchy. - if
*F*and*G*are Cauchy filters and each member of*F*intersects each member of*G*, then*F*∩*G*is Cauchy.

The Cauchy filters on a uniform space have these properties, so every uniform space (hence every metric space) defines a Cauchy space.

## See also

## Notes

- ↑ H. Cartan, "Théorie des filtres",
*CR Acad. Paris*,**205**, (1937) 595–598. - ↑ H. Cartan, "Filtres et ultrafiltres",
*CR Acad. Paris*,**205**, (1937) 777–779.

## 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)
- Stephen Willard,
*General Topology*, (1970) Addison-Wesley Publishing Company, Reading Massachusetts.*(Provides an introductory review of filters in topology.)* - David MacIver,
*Filters in Analysis and Topology*(2004)*(Provides an introductory review of filters in topology and in metric spaces.)* - Burris, Stanley N., and H.P. Sankappanavar, H. P., 1981.
*A Course in Universal Algebra.*Springer-Verlag. ISBN 3-540-90578-2.