Everipedia Logo
Everipedia is now IQ.wiki - Join the IQ Brainlist and our Discord for early access to editing on the new platform and to participate in the beta testing.
Filter (mathematics)

Filter (mathematics)

In mathematics, a filter is a special subset of a partially ordered set. Filters appear in order and lattice theory, but can also be found in topology from where 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 in a partially ordered set (poset), X, is a subset of X 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 doesn't contain any other specific point of the line.

The above interpretations explain conditions 1 and 3: 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 the condition 2 of the general definition of filter (see below).

For, why should two "large enough" things contain a common "large enough" thing?

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:

  1. The empty set cannot contain anything so it will not belong to the filter.
  1. If two subsets,
EandF, both might contain "what is looked for", then so might their intersection.Thus the filter should be closed with respect to finite intersection.
  1. If a set
Emight 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.

General definition

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

  1. F is nonempty.

  2. For every x, y in F, there is some element z in F such that zx and zy. (F is a filter base (see below), or downward directed)

  3. For every x in F and y in P, xy implies that y is in F. (F is an upper set

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 a nonempty upper set that is closed under finite intersection (infima or meet), i.e., for all x, y in F, then xy is also in F.[3] [666666]

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:

  1. if A and B are in F, then so is their intersection. (F is closed under finite intersection)

  2. 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 second property entails that S is in F (since F is a non-empty subset of P (S)).

If the empty set is not in F, we say F is a proper filter. [4]

The first two properties imply that a filter on a set has the finite intersection property. With this definition, a filter on a set is indeed a filter. 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:

  1. B is non-empty and the intersection of any two members of B contains a member of B (B is downward directed).

  2. The empty set is not a member of 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 a member 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 B0 ∈ B, there is a C0 ∈ C such that C0 ⊆ B0. 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 every 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 every 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 of S. 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 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.

Filters in model theory

For every 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 Nx to be the neighbourhood filter point x for X. This means that N**xneighbourhoods of the point x. It can be verified that* N**xis 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 V0 of X is a neighbourhood of x if and only if there exists N0 ∈ N such that N0 ⊆ V0. 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 Bx, means that for every neighbourhood U of x, there is a B0 ∈ B such that B0 ⊆ 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 Cx if and only if C is finer than N. If YX, 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.

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

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.

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(B0) : B0∈B} is the set of all cluster points of* Bclosure of B0 is cl(B0)). Assume that X Binfimum of the set of all cluster points of Blimit superior of Bsupremum 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.

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 or has a cluster point.

  • 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

  • is continuous at if and only if implies.

Cauchy filters

  • To say that a filter base B on X is Cauchy means that for each real number ε>0, there is a B0 ∈ B such that the metric diameter of B0 is less than ε.

  • Take (xn) to be a sequence in metric space X. (xn) is a Cauchy sequence if and only if the filter base {{x**N,* x**N*+1,...} :* 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 AF with (x, y) ∈ U for all x, yA. 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:

  1. for each x in X, the ultrafilter at x, U (x), is Cauchy.

  2. if F is a Cauchy filter, and F is a subset of a filter G, then G is Cauchy.

  3. if F and G are Cauchy filters and each member of F intersects each member of G, then FG is Cauchy.

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

Generalizations

  • Filtrator

Read more

[13] is apparently the world-best reference on the topic of filters.

See also

  • Filtration (mathematics)

  • Filtration (probability theory)

  • Filtration (abstract algebra)

  • Net (mathematics)

  • Generic filter

  • Ideal (set theory)

References

[1]
Citation Linkgallica.bnf.frH. Cartan, "Théorie des filtres", CR Acad. Paris, 205, (1937) 595–598.
Sep 20, 2019, 8:50 PM
[2]
Citation Linkgallica.bnf.frH. Cartan, "Filtres et ultrafiltres", CR Acad. Paris, 205, (1937) 777–779.
Sep 20, 2019, 8:50 PM
[3]
Citation Linkopenlibrary.orgB.A. Davey and H.A. Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press.
Sep 20, 2019, 8:50 PM
[4]
Citation Linkarchive.orgGoldblatt, R. Lectures on the Hyperreals: an Introduction to Nonstandard Analysis. p. 32.
Sep 20, 2019, 8:50 PM
[5]
Citation Linkwww.efnet-math.orgFilters in Analysis and Topology
Sep 20, 2019, 8:50 PM
[6]
Citation Linkwww.thoralf.uwaterloo.caA Course in Universal Algebra.
Sep 20, 2019, 8:50 PM
[12]
Citation Linken.wikipedia.orgThe original version of this page is from Wikipedia, you can edit the page right here on Everipedia.Text is available under the Creative Commons Attribution-ShareAlike License.Additional terms may apply.See everipedia.org/everipedia-termsfor further details.Images/media credited individually (click the icon for details).
Sep 20, 2019, 8:50 PM
[13]
Citation Linkmathematics21.orgAlgebraic General Topology. Volume 1.Victor Porton. 2019.Republication from INFRA-M (Moscow) publisher, with some typos corrected.1st edition
Nov 25, 2019, 6:56 PM