Incubator escapee wiki

Filter (mathematics)

Article Discussion

Template:Short description Template:For {{#invoke:other uses|otheruses}} Template:More footnotes needed

File:Filter vs ultrafilter.svg
The power set lattice of the set Template:Math, with upper set Template:Math 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:Math. Since the latter cannot be extended further, Template:Math 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.

MotivationEdit

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 Template:Math, 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 Template:Math, 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 Template:Math 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.<ref>Template:Cite arXiv</ref> This application generalizes the "locating scheme" to find points that might be hard to write down explicitly.

DefinitionEdit

Template:Anchor A subset Template:Mvar of a partially ordered set Template:Math is a filter or dual ideal if the following are satisfied:<ref name="Davey Priestley 2002"/>

Nontriviality
The set Template:Mvar is non-empty.
Downward directed
For every Template:Math, there is some Template:Math such that Template:Math and Template:Math.
Upward closure
For every Template:Math and Template:Math, the condition Template:Math implies Template:Math.

If, additionally, Template:Math, 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 basesEdit

Template:Anchor A subset Template:Mvar of Template:Mvar is a base or basis for Template:Mvar if the upper set generated by 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 Template:Math is nonempty and 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 Template:Math, the set Template:Math is the smallest filter containing Template:Math, and sometimes written Template:Math. Such a filter is called a principal filter; Template:Math is said to be the principal element of Template:Mvar, or generate Template:Mvar.

RefinementEdit

Suppose Template:Mvar and Template:Mvar are two prefilters on Template:Mvar, and, for each Template:Mvar, there is a Template:Math, such that Template:Math. 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 casesEdit

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 Template:Math, one has Template:Math.<ref name="Davey Priestley 2002">Template:Cite book</ref>

Linear filtersEdit

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:Math of vector subspaces of Template:Mvar such that if Template:Math and Template:Mvar is a vector subspace of Template:Mvar that contains Template:Mvar, then Template:Math and Template:Math.Template:Sfn

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

Filters on a set; subbasesEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} Template:Families of sets Given a set Template:Mvar, the power set Template:Math 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 Template:Math, then so too is Template:Math.
Isotony
Template:Sfn If Template:Math and Template:Math, then Template:Math.

A proper<ref>Template:Cite book</ref>/non-degenerateTemplate:Sfn filter is one that does not contain Template:Math, 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 Template:Math either.

For every subset Template:Mvar of Template:Math, 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 Template:Math, then Template:Mvar admits only the improper filter Template:Math.

Free filtersEdit

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).

ExamplesEdit

See the image at the top of this article for a simple example of filters on the finite poset Template:Math.

Partially order Template:Math, the space of real-valued functions on Template:Math, by pointwise comparison. Then the set of functions "large at infinity,"<math display="block">\left\{f:\lim_{x\to\pm\infty}{f(x)}=\infty\right\}\text{,}</math>is a filter on Template:Math. 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:Math is a filter in Template:Math.

The set Template:Math is a filter in Template:Math. More generally, if Template:Mvar is any directed set, then<math display="block">\{\{k:k\geq N\}:N\in D\}</math>is a filter in Template:Math, called the tail filter. Likewise any net Template:Math generates the eventuality filter Template:Math. A tail filter is the eventuality filter for Template:Math.

The Fréchet filter on an infinite set Template:Mvar is<math display="block">\{A:X\setminus A\text{ finite}\}\text{.}</math>If Template:Math is a measure space, then the collection Template:Math is a filter. If Template:Math, then Template:Math is also a filter; the Fréchet filter is the case where Template:Math is counting measure.

Given an ordinal Template:Mvar, 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 form a filter: the club filter, Template:Math.

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 Template:Math 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 Template:Math denote the set of partial orders of limited cardinality, modulo isomorphism. Partially order Template:Mvar by:

Template:Math if there exists a strictly increasing Template:Math.

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:

Template:Math if there exists an injective linear map Template:Math.<ref>Template:Cite journal</ref>

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

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

Relationship to idealsEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} The dual notion to a filter — that is, the concept obtained by reversing all Template:Math and exchanging Template:Math with Template:Math — 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 theoryEdit

Template:See also For every filter Template:Mvar on a set Template:Mvar, the set function defined by<math display=block>m(A) = \begin{cases} 1 & \text{if }A \in F \\ 0 & \text{if }S \smallsetminus A \in F \\ \text{is undefined} & \text{otherwise} \end{cases}</math>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<math display="block">\left\{\,x \in S : \varphi(x)\,\right\} \in F</math>can be considered somewhat analogous to the statement that Template:Math 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 topologyEdit

{{#invoke:Labelled list hatnote|labelledList|Main article|Main articles|Main page|Main pages}} 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:Math, which are a totally ordered set. Nets generalize the notion of a sequence by replacing Template:Math 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 basesEdit

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

Convergent filters and cluster pointsEdit

A prefilter Template:Mvar converges to a point Template:Mvar, written Template:Math, if and only if Template:Mvar generates a filter Template:Mvar that contains the neighborhood filter Template:Math — explicitly, for every neighborhood Template:Mvar of Template:Mvar, there is some Template:Math such that Template:Math. Less explicitly, Template:Math if and only if Template:Mvar refines Template:Math, and any neighborhood base at Template:Mvar can replace Template:Math 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:Math. The above can also be reversed to characterize the neighborhood filter Template:Math: Template:Math is the finest filter coarser than each filter converging to Template:Mvar.

If Template:Math, 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 alsoEdit

NotesEdit

Template:Reflist Template:Reflist

ReferencesEdit

|CitationClass=web }} (Provides an introductory review of filters in topology and in metric spaces.)

Further readingEdit

Template:Order theory

Retrieved from "https://zalansite.site/mediawiki/index.php?title=Filter_(mathematics)&oldid=12754"