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 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 ...
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 binary ...
(poset). Filters appear in
order Order, ORDER or Orders may refer to: * Categorization, the process in which ideas and objects are recognized, differentiated, and understood * Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of ...
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. Filters on sets were introduced by
Henri Cartan Henri Paul Cartan (; 8 July 1904 – 13 August 2008) was a French mathematician who made substantial contributions to algebraic topology. He was the son of the mathematician Élie Cartan, nephew of mathematician Anna Cartan, oldest brother of c ...
in
1937 Events January * January 1 – Anastasio Somoza García becomes President of Nicaragua. * January 5 – Water levels begin to rise in the Ohio River in the United States, leading to the Ohio River flood of 1937, which continues into ...
and as described in the article dedicated to filters in topology, they were subsequently used by
Nicolas Bourbaki 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 i ...
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 developed in
1922 Events January * January 7 – Dáil Éireann (Irish Republic), Dáil Éireann, the parliament of the Irish Republic, ratifies the Anglo-Irish Treaty by 64–57 votes. * January 10 – Arthur Griffith is elected President of Dáil Éirean ...
by E. H. Moore and Herman L. Smith. 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 binary ...
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 post ...
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 In elementary mathematics, a number line is a picture of a graduated straight line that serves as visual representation of the real numbers. Every point of a number line is assumed to correspond to a real number, and every real number to a po ...
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 ...
: Clearly the
empty set 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 othe ...
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, geometri ...
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. # 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 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 lattices 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 bic ...
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 lo ...
(or meets), 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 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 post ...
\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 Henri Paul Cartan (; 8 July 1904 – 13 August 2008) was a French mathematician who made substantial contributions to algebraic topology. He was the son of the mathematician Élie Cartan, nephew of mathematician Anna Cartan, oldest brother of c ...
, 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 cas ...
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 filter In mathematics, particularly in set theory, if \kappa is a regular uncountable cardinal then \operatorname(\kappa), the filter of all sets containing a club subset of \kappa, is a \kappa-complete filter closed under diagonal intersection call ...
s 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 \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 called ...
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 A measure space is a basic object of measure theory, a branch of mathematics that studies generalized notions of volumes. It contains an underlying set, the subsets of this set that are feasible for measuring (the -algebra) and the method that ...
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 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" 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 theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (math ...
, a branch of
mathematical logic Mathematical logic is the study of 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 forma ...
.


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 called ...
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 setti ...
. Both nets 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 poin ...
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 called ...
is usually indexed by the
natural numbers In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
\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 differently ...
of all nets valued in X is not (it is a
proper class Proper may refer to: Mathematics * Proper map, in topology, a property of continuous function between topological spaces, if inverse images of compact subsets are compact * Proper morphism, in algebraic geometry, an analogue of a proper map f ...
). Neighbourhood bases Let \mathcal_x be the
neighbourhood filter In topology and related areas of mathematics, the neighbourhood system, complete system of neighbourhoods, or neighbourhood filter \mathcal(x) for a point x in a topological space is the collection of all neighbourhoods of x. Definitions Neighbou ...
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 a ...
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 In topology and related areas of mathematics, the neighbourhood system, complete system of neighbourhoods, or neighbourhood filter \mathcal(x) for a point x in a topological space is the collection of all neighbourhoods of x. Definitions Neighb ...
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 converges 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 In topology and related areas of mathematics, the neighbourhood system, complete system of neighbourhoods, or neighbourhood filter \mathcal(x) for a point x in a topological space is the collection of all neighbourhoods of x. Definitions Neighb ...
\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 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 i ...
, 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