Filter (mathematics)

From HandWiki
Short description: In mathematics, a special subset of a partially ordered set
The power set lattice of the set Template:Brace, with upper set Template:Brace colored dark green. This upper set is a filter, and even a principal filter. It is not an ultrafilter, 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) P. Intuitively, a filter F is a subset of P whose members are elements large enough to satisfy some criterion.[1] For instance, if xP, then the set of elements above x is a filter, called the principal filter at x. (If x and y are incomparable elements of P, then neither the principal filter at x nor y is contained in the other.)

Similarly, a filter on a set S contains those subsets that are sufficiently large to contain some given thing. For example, if S is the real line and xS, then the family of sets including x in their interior is a filter, called the neighborhood filter at x. The thing in this case is slightly larger than x, 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 F as a "locating scheme" to find x. In this interpretation, one searches in some space X, and expects F to describe those subsets of X that contain the goal. The goal must be located somewhere; thus the empty set  can never be in F. 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.[2] This application generalizes the "locating scheme" to find points that might be hard to write down explicitly.

Definition

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

Nontriviality
The set F is non-empty.
Downward directed
For every x, yF, there is some zF such that zx and zy.
Upward closure
For every xF and pP, the condition xp implies pF.

If, additionally, FP, then F is said to be a proper filter. Authors in set theory and mathematical logic often require all filters to be proper; this article will eschew that convention.[3] An ultrafilter is a filter contained in no other proper filter.

Filter bases

A subset S of F is a base or basis for F if the upper set generated by S (i.e., the smallest upwards-closed set containing S) is all of F. Every filter is a base for itself.

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

Given pP, 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 F, or generate F.

Refinement

Suppose B and C are two prefilters on P, and, for each cC, there is a bB, such that bc. Then we say that B is finer than (or refines) C; likewise, C is coarser than (or coarsens) B. Refinement is a preorder on the set of prefilters. In fact, if C also refines B, then B and C 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, yF, one has xyF.[4]

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 X is a family B of vector subspaces of X such that if A, BB and C is a vector subspace of X that contains A, then ABB and CB.[5]

A linear filter is proper if it does not contain Template:Brace.[5]

Filters on a set; subbases

Main page: Filter (set theory)

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

Closure under finite intersections
If A, BF, then so too is ABF.
Isotony
[6] If AF and ABS, then BF.

A proper[7]/non-degenerate[8] filter is one that does not contain , and these three conditions (including non-degeneracy) are Henri Cartan's original definition of a filter.[9][10] 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 T of P(S), there is a smallest filter F containing T. As with prefilters, T is said to generate or span F; a base for F is the set U of all finite intersections of T. The set T is said to be a filter subbase when F (and thus U) is proper.

Proper filters on sets have the finite intersection property.

If S = ∅, then S admits only the improper filter Template:Brace.

Free filters

A filter is said to be a free 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 § Examples).

Examples

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

Partially order Template:MathbbTemplate:Mathbb, the space of real-valued functions on Template:Mathbb, by pointwise comparison. Then the set of functions "large at infinity,"[math]\displaystyle{ \left\{f:\lim_{x\to\pm\infty}{f(x)}=\infty\right\}\text{,} }[/math]is a filter on Template:MathbbTemplate:Mathbb. One can generalize this construction quite far by compactifying the domain and completing the codomain: if X is a set with distinguished subset S and Y is a poset with distinguished element m, then Template:Brace is a filter in XY.

The set Template:Brace is a filter in P(Template:Mathbb). More generally, if D is any directed set, then[math]\displaystyle{ \{\{k:k\geq N\}:N\in D\} }[/math]is a filter in P(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 X is[math]\displaystyle{ \{A:X\setminus A\text{ finite}\}\text{.} }[/math]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 a, a subset of a is called a club if it is closed in the order topology of a but has net-theoretic limit a. The clubs of a form a filter: the club filter♣(a).

The previous construction generalizes as follows: any club C is also a collection of dense subsets (in the ordinal topology) of a, and ♣(a) meets each element of C. Replacing C with an arbitrary collection  of dense sets, there "typically" exists a filter meeting each element of , called a generic filter. For countable , the Rasiowa–Sikorski lemma implies that such a filter must exist; for "small" uncountable , 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 P by:

AB if there exists a strictly increasing f : AB.

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

AB if there exists an injective linear map f : AB.[11]

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

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

Relationship to ideals

Main page: Ideal (order theory)

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 F on a set S, the set function defined by[math]\displaystyle{ 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 F is an ultrafilter. Therefore, the statement[math]\displaystyle{ \left\{\,x \in S : \varphi(x)\,\right\} \in F }[/math]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 proofs) in the theory of ultraproducts in model theory, a branch of mathematical logic.

In topology

Main page: Filters 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 X, whereas sequences and nets rely on other directed sets. For this reason, the collection of all filters on X is always a set, whereas the collection of all X-valued nets is a proper class.

Neighborhood bases

Any point x in the topological space X defines a neighborhood filter or system Nx: namely, the family of all sets containing x in their interior. A set N of neighborhoods of x is a neighborhood base at x if N generates Nx. Equivalently, SX is a neighborhood of x if and only if there exists NN such that NS.

Convergent filters and cluster points

A prefilter B converges to a point x, written Bx, if and only if B generates a filter F that contains the neighborhood filter Nx — explicitly, for every neighborhood U of x, there is some VB such that VU. Less explicitly, Bx if and only if B refines Nx, and any neighborhood base at x can replace Nx in this condition. Clearly, every neighborhood base at x converges to x.

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

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

See also

Notes

  1. Koutras et al. 2021.
  2. Igarashi, Ayumi; Zwicker, William S. (16 February 2021). "Fair division of graphs and of tangled cakes". arXiv:2102.08560 [math.CO].
  3. 3.0 3.1 Dugundji 1966, pp. 211-213.
  4. Davey, B. A.; Priestley, H. A. (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press. p. 184. 
  5. 5.0 5.1 Bergman & Hrushovski 1998.
  6. Dolecki & Mynard 2016, pp. 27-29.
  7. Goldblatt, R. Lectures on the Hyperreals: an Introduction to Nonstandard Analysis. p. 32. https://archive.org/stream/springer_10.1007-978-1-4612-0615-6/10.1007-978-1-4612-0615-6#page/n31/mode/2up/search/proper+filter. 
  8. Narici & Beckenstein 2011, pp. 2-7.
  9. Cartan 1937a.
  10. Cartan 1937b.
  11. Bumby, R. T. (1965-12-01). "Modules which are isomorphic to submodules of each other" (in en). Archiv der Mathematik 16 (1): 184–185. doi:10.1007/BF01220018. ISSN 1420-8938. https://doi.org/10.1007/BF01220018. 

References

Further reading

  • Bergman, George M.; Hrushovski, Ehud (1998). "Linear ultrafilters". Communications in Algebra 26 (12): 4079–4113. doi:10.1080/00927879808826396.