Filter (mathematics)

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
The powerset lattice of the set with the upper set colored dark green. It is a filter, and even a principal filter. It is not an ultrafilter, as it can be extended to the larger nontrivial filter by including also the light green elements. Since cannot be extended any further, it is an ultrafilter.

In mathematics, a filter or order 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 which they originate. The dual notion of a filter is an order 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[edit]

1. Intuitively, a filter in a partially ordered set (poset), is a subset of that includes as members those elements that are large enough to satisfy some given criterion. For example, if is an element of the poset, then the set of elements that are above is a filter, called the principal filter at (If and are incomparable elements of the poset, then neither of the principal filters at and 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 is one of its points, then the family of sets that include in their interior is a filter, called the filter of neighbourhoods of The thing in this case is slightly larger than 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 call a filter the collection of subsets of that might contain "what is looked for". Then this "filter" should possess the following natural structure:

  1. A locating scheme must be non-empty in order to be of any use at all.
  2. If two subsets, and both might contain "what is looked for", then so might their intersection. Thus the filter should be closed with respect to finite intersection.
  3. If a set 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 of the space can be used in deciding whether "what is looked for" might lie in 

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 .[3] The entire space definitely contains almost-all elements in it; If some contains almost all elements of , then any superset of it definitely does; and if two subsets, and contain almost-all elements of , then so does their intersection. In a measure-theoretic terms, the meaning of " contains almost-all elements of " is that the measure of is 0.

General definition: Filter on a partially ordered set[edit]

A subset of a partially ordered set is an order filter if the following conditions hold:

  1. is non-empty.
  2. is downward directed: For every there is some such that and
  3. is an upper set or upward-closed: For every and implies that

is said to be proper if in addition is not equal to the whole set 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 of a lattice 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 it is also the case that [4] A subset of is a filter basis if the upper set generated by is all of Note that every filter is its own basis.

The smallest filter that contains a given element is a principal filter and is a principal element in this situation. The principal filter for is just given by the set and is denoted by prefixing with an upward arrow:

The dual notion of a filter, that is, 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[edit]

Definition of a filter[edit]

There are two competing definitions of a "filter on a set," both of which require that a filter be a dual ideal.[5] 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.
Definition: A dual ideal[5] on a set is a non-empty subset of with the following properties:
  1. is closed under finite intersections: If then so is their intersection.
    • This property implies that if then has the finite intersection property.
  2. is upward closed/isotone:[6] If and then for all subsets
    • This property entails that (since is a non-empty subset of ).

Given a set a canonical partial ordering can be defined on the powerset by subset inclusion, turning into a lattice. A "dual ideal" is just a filter with respect to this partial ordering. Note that if then there is exactly one dual ideal on which is

Filter definition 1: Dual ideal[edit]

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

Definition: A filter on a set is a dual ideal on Equivalently, a filter on is just a filter with respect the canonical partial ordering described above.

Filter definition 2: Proper dual ideal[edit]

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: A filter[5] on a set is a dual ideal on with the following additional property:
  1. is proper[7]/non-degenerate:[8] The empty set is not in (i.e. ).
Note: This article does not require that a filter be proper.

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

Filter bases, subbases, and comparison[edit]

Filter bases and subbases

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

Given a filter base the filter generated or spanned by is defined as the minimum filter containing It is the family of all those subsets of which are supersets of some member(s) of 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 of there is a smallest (possibly nonproper) filter containing called the filter generated or spanned by Similarly as for a filter spanned by a filter base, a filter spanned by a subset is the minimum filter containing It is constructed by taking all finite intersections of which then form a filter base for This filter is proper if and only if every finite intersection of elements of is non-empty, and in that case we say that is a filter subbase.

Finer/equivalent filter bases

If and are two filter bases on one says is finer than (or that is a refinement of ) if for each there is a such that If also is finer than one says that they are equivalent filter bases.

  • If and are filter bases, then is finer than if and only if the filter spanned by contains the filter spanned by Therefore, and are equivalent filter bases if and only if they generate the same filter.
  • For filter bases and if is finer than and is finer than then is finer than 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.

Examples[edit]

  • Let be a set and be a non-empty subset of Then is a filter base. The filter it generates (that is,, the collection of all subsets containing ) is called the principal filter generated by
  • 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 is the set of all subsets of that have finite complement. A filter on is free if and only if it includes the Fréchet filter.
    • More generally, if is a measure space for which the collection of all such that forms a filter. The Fréchet filter is the case where and is the counting measure.
  • Every uniform structure on a set is a filter on
  • 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[edit]

For every filter on a set 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[edit]

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.

Throughout, will be a topological space and

Neighbourhood bases[edit]

Take to be the neighbourhood filter at point for This means that is the set of all topological neighbourhoods of the point It can be verified that is a filter. A neighbourhood system is another name for a neighbourhood filter. To say that is a neighbourhood base at for means that each subset of is a neighbourhood of if and only if there exists Every neighbourhood base at is a filter base that generates the neighbourhood filter at

Convergent filter bases[edit]

To say that a filter base converges to denoted means that for every neighbourhood of there is a such that In this case, is called a limit of and is called a convergent filter base.

Every neighbourhood base of converges to

  • If is a neighbourhood base at and is a filter base on then if is finer than If is the upward closed neighborhood filter, then the converse holds as well: any basis of a convergent filter refines the neighborhood filter.
  • If a point is called a limit point of in if and only if each neighborhood of in intersects This happens if and only if there is a filter base of subsets of that converges to in

For the following are equivalent:

  • (i) There exists a filter base whose elements are all contained in such that
  • (ii) There exists a filter such that is an element of and
  • (iii) The point lies in the closure of

Indeed:

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

(ii) implies (iii): if is any open neighborhood of then by the definition of convergence, contains an element of ; since also and have non-empty intersection.

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

Clustering[edit]

A filter base on is said to cluster at (or have as a cluster point) if and only if each element of has non-empty intersection with each neighbourhood of

  • If a filter base clusters at and is finer than a filter base then also clusters at
  • Every limit of a filter base is also a cluster point of the base.
  • A filter base that has as a cluster point may not converge to 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 the set is the set of all cluster points of (the closure of is Assume that is a complete lattice.

  • The limit inferior of is the infimum of the set of all cluster points of
  • The limit superior of is the supremum of the set of all cluster points of
  • 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[edit]

If is a topological space then:

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

Functions between topological spaces[edit]

Let and be topological spaces, let be a filter base on and let be a function. The image of under denoted by is defined as the set which necessarily forms a filter base on

is continuous at if and only if for every filter base on

Cauchy filters[edit]

Let be a metric space.

  • To say that a filter base on is Cauchy means that for each real number there is a such that the metric diameter of is less than
  • Take to be a sequence in metric space Then is a Cauchy sequence if and only if the filter base is Cauchy.

More generally, given a uniform space a filter on is called a Cauchy filter if for every entourage there is an with In a metric space this agrees with the previous definition. 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 the ultrafilter at is Cauchy.
  2. if is a Cauchy filter, and is a subset of a filter then is Cauchy.
  3. if and are Cauchy filters and each member of intersects each member of then 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[edit]

Notes[edit]

  1. ^ H. Cartan, "Théorie des filtres", CR Acad. Paris, 205, (1937) 595–598.
  2. ^ H. Cartan, "Filtres et ultrafiltres", CR Acad. Paris, 205, (1937) 777–779.
  3. ^ Igarashi, Ayumi; Zwicker, William S. (2021-02-16). "Fair division of graphs and of tangled cakes". arXiv:2102.08560 [math.CO].
  4. ^ B.A. Davey and H.A. Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press. p. 184.
  5. ^ a b c Dugundji 1966, pp. 211–213.
  6. ^ Dolecki & Mynard 2016, pp. 27–29.
  7. ^ Goldblatt, R. Lectures on the Hyperreals: an Introduction to Nonstandard Analysis. p. 32.
  8. ^ Narici & Beckenstein 2011, pp. 2–7.

References[edit]

Further reading[edit]

  • George M. Bergman; Ehud Hrushovski: Linear ultrafilters, Comm. Alg., 26 (1998) 4079–4113.