HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a filter or order filter is a special subset of a
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a bina ...
(poset). Filters appear in order and
lattice theory A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum (also called a least upper bou ...
, but can also be found in
topology In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
, from which they originate. The dual notion of a filter is an
order ideal In mathematical order theory, an ideal is a special subset of a partially ordered set (poset). Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different not ...
. Filters on sets were introduced by Henri Cartan in 1937 and as described in the article dedicated to
filters in topology Filters in topology, a subfield of mathematics, can be used to study topological spaces and define all basic topological notions such a convergence, continuity, compactness, and more. Filters, which are special families of subsets of some give ...
, they were subsequently used by Nicolas Bourbaki in their book ''
Topologie Générale Nicolas Bourbaki () is the collective pseudonym of a group of mathematicians, predominantly French alumni of the École normale supérieure - PSL (ENS). Founded in 1934–1935, the Bourbaki group originally intended to prepare a new textbook in ...
'' as an alternative to the related notion of a
net Net or net may refer to: Mathematics and physics * Net (mathematics), a filter-like topological generalization of a sequence * Net, a linear system of divisors of dimension 2 * Net (polyhedron), an arrangement of polygons that can be folded up ...
developed in 1922 by
E. H. Moore Eliakim Hastings Moore (; January 26, 1862 – December 30, 1932), usually cited as E. H. Moore or E. Hastings Moore, was an American mathematician. Life Moore, the son of a Methodist minister and grandson of US Congressman Eliakim H. Moore, di ...
and
Herman L. Smith Herman Lyle Smith (July 7, 1892 – 1950) was an American mathematician, the co-discoverer, with E. H. Moore, of nets, and also a discoverer of the related notion of filters independently of Henri Cartan. Born in Pittwood, Illinois, Smith recei ...
. Order filters are generalizations of this notion from sets to the more general setting of
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a bina ...
s. For information on order filters in the special case where the poset consists of the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
ordered by
set inclusion In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
, see the article
Filter (set theory) In mathematics, a filter on a set X is a Family of sets, family \mathcal of subsets such that: # X \in \mathcal and \emptyset \notin \mathcal # if A\in \mathcal and B \in \mathcal, then A\cap B\in \mathcal # If A,B\subset X,A\in \mathcal, and A ...
.


Motivation

1. Intuitively, a filter in a partially ordered set (), P, is a subset of P 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 . 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 in this case is slightly larger than x, 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 A general officer is an officer of high rank in the armies, and in some nations' air forces, space forces, and marines or naval infantry. In some usages the term "general officer" refers to a rank above colonel."general, adj. and n.". OED O ...
: 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 "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 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: #A locating scheme must be non-empty in order to be of any use at all. #If two subsets, E and F, both might contain "what is looked for", then so might their intersection. Thus the filter should be closed with respect to finite intersection. #If a set E 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 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 In mathematics, general topology is the branch of topology that deals with the basic set-theoretic definitions and constructions used in topology. It is the foundation of most other branches of topology, including differential topology, geomet ...
and logic. 3. A common use for a filter is to define properties that are satisfied by "almost all" elements of some topological space X. The entire space X definitely contains almost-all elements in it; If some E\subseteq X contains almost all elements of X, then any superset of it definitely does; and if two subsets, E and F, contain almost-all elements of X, then so does their intersection. In a measure-theoretic terms, the meaning of "E contains almost-all elements of X" is that the measure of X\smallsetminus E is 0.


General definition: Filter on a partially ordered set

A subset F of a partially ordered set (P, \leq) is an or if the following conditions hold: # F is
non-empty In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other t ...
. # F is downward
directed Director may refer to: Literature * ''Director'' (magazine), a British magazine * ''The Director'' (novel), a 1971 novel by Henry Denker * ''The Director'' (play), a 2000 play by Nancy Hasty Music * Director (band), an Irish rock band * ''D ...
: For every x, y \in F, there is some z \in F such that z \leq x and z \leq y. # F is an
upper set In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger ...
or upward-closed: For every x \in F and p \in P, x \leq p implies that p \in F. F is said to be a if in addition F is not equal to the whole set P. Depending on the author, the term filter is either a synonym of order filter or else it refers to a 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
lattice Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an orna ...
s only. In this case, the above definition can be characterized by the following equivalent statement: A subset F of a lattice (P, \leq) is a filter,
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is b ...
it is a non-empty upper set that is closed under finite
infima In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...
(or
meet Meet may refer to: People with the name * Janek Meet (born 1974), Estonian footballer * Meet Mukhi (born 2005), Indian child actor Arts, entertainment, and media * ''Meet'' (TV series), an early Australian television series which aired on ABC du ...
s), that is, for all x, y \in F, it is also the case that x \wedge y \in F. A subset S of F is a filter basis if the upper set generated by S is all of F. Note that every filter is its own basis. The smallest filter that contains a given element p \in P is a principal filter and p is a in this situation. The principal filter for p is just given by the set \ and is denoted by prefixing p with an upward arrow: \uparrow p. The dual notion of a filter, that is, the concept obtained by reversing all \,\leq\, and exchanging \,\wedge\, with \,\vee, 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
ultrafilter In the mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") P is a certain subset of P, namely a maximal filter on P; that is, a proper filter on P that cannot be enlarged to a bigger proper filter o ...
s. Applying these definitions to the case where X is a
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
and P is the set of all
vector subspace In mathematics, and more specifically in linear algebra, a linear subspace, also known as a vector subspaceThe term ''linear subspace'' is sometimes used for referring to flats and affine subspaces. In the case of vector spaces over the reals, l ...
s of X ordered by inclusion \,\subseteq\, gives rise to the notion of and . Explicitly, a on a vector space X is a family \mathcal of vector subspaces of X such that if A, B \in \mathcal and if C is a vector subspace of X that contains A, then A \cap B, C \in \mathcal. A linear filter is called if it does not contain \; a on X is a maximal proper linear filter on X.


Filter on a set


Definition of a filter

There are two competing definitions of a "filter on a set," both of which require that a filter be a . One definition defines "filter" as a synonym of "dual ideal" while the other defines "filter" to mean a dual ideal that is also . :Warning: It is recommended that readers always check how "filter" is defined when reading mathematical literature. A on a set S is a non-empty subset F of \wp(S) with the following properties:
  1. F is closed under finite intersections: If A, B \in F, then so is their intersection. * This property implies that if \varnothing \not\in F then F has the
    finite intersection property In general topology, a branch of mathematics, a non-empty family ''A'' of subsets of a set X is said to have the finite intersection property (FIP) if the intersection over any finite subcollection of A is non-empty. It has the strong finite inters ...
    .
  2. F is upward closed/isotone: If A \in F and A \subseteq B, then B \in F, for all subsets B \subseteq S. * This property entails that S \in F (since F is a non-empty subset of \wp(S)).
Given a set S, a canonical partial ordering \,\subseteq\, can be defined on the powerset \wp(S) by subset inclusion, turning (\wp(S), \subseteq) into a lattice. A "dual ideal" is just a filter with respect to this partial ordering. Note that if S = \varnothing then there is exactly one dual ideal on S, which is \wp(S) = \. A filter on a set may be thought of as representing a "collection of large subsets".


Filter definitions

The article uses the following definition of "filter on a set." Definition as a dual ideal: A filter on a set S is a dual ideal on S. Equivalently, a filter on S is just a filter with respect the canonical partial ordering (\wp(S), \subseteq) described above. 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 contain the empty set: Original/Alternative definition as a dual ideal: A filter on a set S is a dual ideal on S with the following additional property:
  1. F is proper/non-degenerate: The empty set is not in F (i.e. \varnothing \not\in F).
:Note: This article does require that a filter be proper. The only non-proper filter on S is \wp(S). Much mathematical literature, especially that related to
Topology In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
, defines "filter" to mean a dual ideal.


Filter bases, subbases, and comparison

Filter bases and subbases A subset B of \wp(S) is called a prefilter, filter base, or filter basis if B is non-empty and the intersection of any two members of B is a superset of some member(s) of B. If the empty set is not a member of B, we say 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 those subsets of S which are supersets of some member(s) 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. For every subset T of \wp(S) there is a smallest (possibly non-proper) filter F containing T, called the filter generated or spanned by T. Similarly as for a filter spanned by a , a filter spanned by a T is the minimum filter containing 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. Finer/equivalent filter bases If B and C are two filter bases on S, one says C is than B (or that C is a of B) if for each B_0 \in B, there is a C_0 \in C such that C_0 \subseteq B_0. 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 In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special c ...
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. 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.


Examples

A filter in a
poset In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary r ...
can be created using the Rasiowa–Sikorski lemma, which is often used in forcing. Other filters include club filters and
generic filter In the mathematical field of set theory, a generic filter is a kind of object used in the theory of forcing, a technique used for many purposes, but especially to establish the independence of certain propositions from certain formal theories, such ...
s. The set \ is called a of the sequence of natural numbers (1, 2, 3, \dots). A filter base of tails can be made of any
net Net or net may refer to: Mathematics and physics * Net (mathematics), a filter-like topological generalization of a sequence * Net, a linear system of divisors of dimension 2 * Net (polyhedron), an arrangement of polygons that can be folded up ...
\left(x_\alpha\right)_ using the construction \left\, where the filter that this filter base generates is called the net's Therefore, all nets generate a filter base (and therefore a filter). Since all
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
s are nets, this holds for sequences as well. Let S be a set and C be a non-empty subset of S. Then \is a filter base. The filter it generates (that is, 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 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 In mathematics, the Fréchet filter, also called the cofinite filter, on a set X is a certain collection of subsets of X (that is, it is a particular subset of the power set of X). A subset F of X belongs to the Fréchet filter if and only if the c ...
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 includes the Fréchet filter. More generally, if (X, \mu) is a measure space for which \mu(X) = \infty, the collection of all A \subseteq X such that \mu(X \smallsetminus A) < \infty forms a filter. The Fréchet filter is the case where X = S and \mu is the
counting measure In mathematics, specifically measure theory, the counting measure is an intuitive way to put a measure on any set – the "size" of a subset is taken to be the number of elements in the subset if the subset has finitely many elements, and infinity ...
. Every
uniform structure In the mathematical field of topology, a uniform space is a set with a uniform structure. Uniform spaces are topological spaces with additional structure that is used to define uniform properties such as completeness, uniform continuity and unifor ...
on a set X is a filter on X \times X.


Filters in model theory

For every filter F on a set S the set function defined by m(A) \quad = \begin 1 & \textA \in F \\ 0 & \textS \smallsetminus A \in F \\ \text & \text \end is finitely additive — a "
measure Measure may refer to: * Measurement, the assignment of a number to a characteristic of an object or event Law * Ballot measure, proposed legislation in the United States * Church of England Measure, legislation of the Church of England * Mea ...
" if that term is construed rather loosely. Therefore, the statement \left\ \in F can be considered somewhat analogous to the statement that \varphi holds "almost everywhere". That interpretation of membership in a filter is used (for motivation, although it is not needed for actual ) in the theory of
ultraproduct The ultraproduct is a mathematical construction that appears mainly in abstract algebra and mathematical logic, in particular in model theory and set theory. An ultraproduct is a quotient of the direct product of a family of structures. All factor ...
s in
model theory In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
, a branch of
mathematical logic Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
.


Filters in topology

In
topology In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
and analysis, filters are used to define convergence in a manner similar to the role of
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
s in a
metric space In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general settin ...
. Both
net Net or net may refer to: Mathematics and physics * Net (mathematics), a filter-like topological generalization of a sequence * Net, a linear system of divisors of dimension 2 * Net (polyhedron), an arrangement of polygons that can be folded up ...
s and filters provide very general contexts to unify the various notions of
limit Limit or Limits may refer to: Arts and media * ''Limit'' (manga), a manga by Keiko Suenobu * ''Limit'' (film), a South Korean film * Limit (music), a way to characterize harmony * "Limit" (song), a 2016 single by Luna Sea * "Limits", a 2019 ...
to arbitrary
topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called po ...
s. A
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
is usually indexed by the natural numbers \N, which are a
totally ordered set In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive) ...
. Nets generalize the notion of a sequence by requiring the index set simply be a
directed set In mathematics, a directed set (or a directed preorder or a filtered set) is a nonempty set A together with a reflexive and transitive binary relation \,\leq\, (that is, a preorder), with the additional property that every pair of elements has ...
. If working only with certain categories of topological spaces, such as
first-countable space In topology, a branch of mathematics, a first-countable space is a topological space satisfying the "first axiom of countability". Specifically, a space X is said to be first-countable if each point has a countable neighbourhood basis (local base) ...
s for instance, sequences suffice to characterize most topological properties, but this is not true in general. However, filters (as well as nets) do always suffice to characterize most topological properties. An advantage to using filters is that they do not involve any set other than X (and its subsets) whereas sequences and nets rely on directed sets that may be unrelated to X. Moreover, the set of all filters on X is a
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
whereas the
class Class or The Class may refer to: Common uses not otherwise categorized * Class (biology), a taxonomic rank * Class (knowledge representation), a collection of individuals or objects * Class (philosophy), an analytical concept used differentl ...
of all nets valued in X is not (it is a proper class). Neighbourhood bases Let \mathcal_x be the neighbourhood filter at point x in a topological space X. This means that \mathcal_x is the set of all topological
neighbourhood A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; see spelling differences) is a geographically localised community within a larger city, town, suburb or rural are ...
s of the point x. It can be verified that \mathcal_x is a filter. A neighbourhood system is another name for a neighbourhood filter. A family \mathcal of neighbourhoods of x is a neighbourhood base at x if \mathcal generates the filter \mathcal_x. This means that each subset S of X is a neighbourhood of x if and only if there exists N \in \mathcal such that N \subseteq S. Convergent filters and cluster points We say that a filter base B
converge Converge may refer to: * Converge (band), American hardcore punk band * Converge (Baptist denomination), American national evangelical Baptist body * Limit (mathematics) * Converge ICT, internet service provider in the Philippines *CONVERGE CFD s ...
s to a point x, written B \to x, if the neighbourhood filter \mathcal_x is contained in the filter F generated by B; that is, if B is finer than \mathcal_x. In particular, a filter F (which is a filter base that generates itself) converges to x if \mathcal_x \subseteq F. Explicitly, to say that a filter base B converges to x means that for every neighbourhood U of x, there is a B_0 \in B such that B_0 \subseteq U. If a filter base B converges to a point x, then x is called a
limit Limit or Limits may refer to: Arts and media * ''Limit'' (manga), a manga by Keiko Suenobu * ''Limit'' (film), a South Korean film * Limit (music), a way to characterize harmony * "Limit" (song), a 2016 single by Luna Sea * "Limits", a 2019 ...
(point) of B and B is called a convergent filter base. A filter base B on X is said to cluster at x (or have x as a
cluster point In mathematics, a limit point, accumulation point, or cluster point of a set S in a topological space X is a point x that can be "approximated" by points of S in the sense that every neighbourhood of x with respect to the topology on X also contai ...
) if and only if each element of B has non-empty intersection with each neighbourhood of x. Every limit point is a cluster point but the converse is not true in general. However, every cluster point of an filter is a limit point. By definition, every neighbourhood base \mathcal at a given point x generates \mathcal_x, so \mathcal converges to x. If C is a filter base on X then C \to x if C is finer than any neighbourhood base at x. For the neighborhood filter at that point, the converse holds as well: any basis of a convergent filter refines the neighborhood filter.


See also

* * * * *


Notes


References

* Nicolas Bourbaki, General Topology (Topologie Générale), (Ch. 1-4): Provides a good reference for filters in general topology (Chapter I) and for Cauchy filters in uniform spaces (Chapter II) * * * * * * * * * (Provides an introductory review of filters in topology and in metric spaces.) * * (Provides an introductory review of filters in topology.)'' * *


Further reading

* {{Order theory General topology Order theory