Filter (mathematics)

From Wikipedia, the free encyclopedia

In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. 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.

1 General definition
2 Filter on a set
3 See also
4 References

[edit] General definition

A non-empty 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)
For every x in F and y in P, x ≤ y 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 is often taken as part of 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 non-empty subset F of a lattice (P,≤) is a filter, if and only if it is an upper set that is closed under finite meets (infima), 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: $\uparrow p$ .

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.

[edit] 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 subset of P(S) with the following properties:

S is in F. (F is non-empty)
The empty set is not in F. (F is proper)
If A and B are in F, then so is their intersection. (F is closed under finite meets)
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 an upper set)

The first three 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, as long as the set context is clear, the shorter name is sufficient.

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

The intersection of any two sets of B contains a set of B
B is non-empty and the empty set is not in B

A filter base B can be turned into a (proper) filter by including all sets of P(S) which contain a set of B. The resulting filter base is said to be generated by or spanned by filter base B. Thus, analysis is often concerned with filter bases rather than filters. Since all filters are filter bases, any results on filter bases will also hold with filters.

If B and C are two filter bases on S, to say that C is finer than B (or that C is a refinement of B) means that for each B₀ ∈ B, there is a C₀ ∈ C such that C₀ ⊆ B₀.

For filter bases B and C, if B is finer than C and C is finer than B then B and C are said to be equivalent filter bases.
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.

Given a subset T of P(S) we can ask whether there exists a smallest filter F containing T. Such a filter exists if and only if the finite intersection of subsets of T is non-empty. We call T a subbase of F and say F is generated by T. F can be constructed by taking all finite intersections of T which is then filter base for F.

[edit] Examples

A simple example of a filter is the set of all subsets of S that include a particular non-empty subset C of S. Such a filter is called the principal filter generated by C.

The Fréchet filter on an infinite set S is the set of all subsets of S that have finite complement.

A 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 $\{ \{ N, N+1, N+2, \dots \} : N \in \{1,2,3,\dots\} \}$ is called a filter base of tails of the sequence of natural numbers $(1,2,3,\dots)$ . A filter base of tails can be made of any net $(x_\alpha)_{\alpha \in A}$ using the construction $\{ \{ x_\alpha : \alpha \in A, \alpha_0 \leq a \} : \alpha_0 \in A \}\,$ . Therefore, all nets generate a filter base (and therefore a filter). Since all sequences are nets, this holds for sequences as well.

[edit] Filters in model theory

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

$m(A)=\left\{ \begin{matrix} \,1 & \mbox{if }A\in F \\ \,0 & \mbox{if }S\setminus A\in F \\ \,\mbox{undefined} & \mbox{otherwise} \end{matrix} \right.$

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

$\left\{\,x\in S: \varphi(x)\,\right\}\in F$

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.

[edit] 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, a net 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 is conceptually the same as the limit of a sequence.

An advantage to using filters is that many results can be shown without using the axiom of choice.

[edit] Neighbourhood Bases

Take a topological space T and a point x ∈ T.

Take N_x to be the neighbourhood filter at point x for T. This means that N_x is the set of all topological neighbourhoods of point x. It can be verified that N_x is a filter. A neighborhood system is another name for a neighborhood filter.

To say that N is a neighbourhood base at x for T means that for all V₀ ∈ N_x, there exists a N₀ ∈ N such that N₀ ⊆ V₀. Note that every neighbourhood base is a filter base.

[edit] Convergent Filter Bases

Take a topological space T and a point x ∈ T.

To say that filter base B converges to x, denoted B → x, means that for every neighbourhood U of x, there is a B₀ ∈ B such that B₀ ⊆ U. In this case, x is called a limit point of B and B is called a convergent filter base.
- For every neighbourhood base N of x, N → x.
- If N is a neighbourhood base of p and C is a filter base on T, then C → x if and only if C is finer than N.
- For X ⊆ T, to say that p is a limit point of X in T means that for each neighborhood U of p in T, U∩(A - {p})≠∅.
- For X ⊆ T, p is a limit point of X in T if and only if there exists a filter base B on A - {p} such that B → p.

[edit] Clustering

Take a topological space T and a point x ∈ T.

To say that x is a cluster point for filter base B on T means that for each B₀ ∈ B and for each neighbourhood U of x in T, B∩U≠∅. In this case, B is said to cluster at point x.
- For filter base B such that B → x, the limit point x is also a cluster point.
- For filter base B with cluster point x, it is not the case that x is necessarily a limit point.
- For a filter base B that clusters at point x, there is a filter base C that is finer than filter base B that converges to x.
- For a filter base B, the set ∩{cl(B₀) : B₀∈B} is the set of all cluster points of B (note: cl(B₀) is the closure of B₀). Assume that T is a partially ordered set.
  - 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.

[edit] Properties of a Topological Space

Take a topological space T.

T is a Hausdorff space if and only if for every filter base B on T, B→p and B→q implies p=q (i.e., every filter base has a unique limit point).
T is compact if and only if every filter base on X clusters.
T is compact if and only if every filter base on X is a subset of a convergent filter base.
T is compact if and only if every ultrafilter on X converges.

[edit] Functions on Topological Spaces

Take topological spaces X and Y and subset E ⊆ X. Take a filter base B on E and a function $f : E \to Y$ . The image of B under f is f[B] is the set $\{ f(x) : x \in B \}$ . The image f[B] forms a filter base on Y.

f is continuous at x if and only if $F \to x$ implies $f(F) \to f(x)$ .

[edit] Metric Spaces

Take a metric space X with metric d.

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

[edit] Filters in uniform spaces

Given a uniform space X, a filter F on X is called Cauchy filter if for every U in the entourage, there is an $A \in F$ with $(x, y) \in U$ for every $x, y \in A$ . In a metric space this takes the form F is Cauchy if for every $\epsilon > 0 \ \ \exists A \in F \ \ \mathrm{diam}(A) < \epsilon$ . X is said to be complete if every Cauchy filter converges.

Let $F \subseteq G , \ \ G \to x, \ F$ Cauchy. Then $F \to x$ . Thus every compact uniformity is complete. Further, a uniformity is compact if and only if it is complete and totally bounded.

[edit] See also

[edit] References

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

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.

Retrieved from "http://en.wikipedia.org../../../f/i/l/Filter_%28mathematics%29.html"

Category: Order theory

Filter (mathematics)

From Wikipedia, the free encyclopedia

Contents

[edit] General definition

[edit] Filter on a set

[edit] Examples

[edit] Filters in model theory

[edit] Filters in topology

[edit] Neighbourhood Bases

[edit] Convergent Filter Bases

[edit] Clustering

[edit] Properties of a Topological Space

[edit] Functions on Topological Spaces

[edit] Metric Spaces

[edit] Filters in uniform spaces

[edit] See also

[edit] References

Views

Navigation

interaction

Search

In other languages