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 (),
is a subset of
that includes as members those elements that are large enough to satisfy some given criterion. For example, if
is an element of the poset, then the set of elements that are above
is a filter, called the principal filter at
(If
and
are incomparable elements of the poset, then neither of the principal filters at
and
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
is one of its points, then the family of sets that include
in their
interior is a filter, called the filter of neighbourhoods of
The in this case is slightly larger than
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
call a filter the collection of subsets of
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,
and
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
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
of the space
can be used in deciding whether "what is looked for" might lie in
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
The entire space
definitely contains almost-all elements in it; If some
contains almost all elements of
then any superset of it definitely does; and if two subsets,
and
contain almost-all elements of
then so does their intersection. In a
measure-theoretic terms, the meaning of "
contains almost-all elements of
" is that the measure of
is 0.
General definition: Filter on a partially ordered set
A subset
of a partially ordered set
is an or if the following conditions hold:
#
is
non-empty.
#
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
there is some
such that
and
#
is an
upper set or upward-closed: For every
and
implies that
is said to be a if in addition
is not equal to the whole set
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
of a lattice
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
it is also the case that
A subset
of
is a filter basis if the upper set generated by
is all of
Note that every filter is its own basis.
The smallest filter that contains a given element
is a principal filter and
is a in this situation.
The principal filter for
is just given by the set
and is denoted by prefixing
with an upward arrow:
The
dual notion of a filter, that is, 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
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
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
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
ordered by inclusion
gives rise to the notion of and . Explicitly, a on a vector space
is a family
of vector subspaces of
such that if
and if
is a vector subspace of
that contains
then
A linear filter is called if it does not contain
a on
is a maximal proper linear filter on
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
is a non-empty subset
of
with the following properties:
- is closed under finite intersections: If then so is their intersection.
* This property implies that if then 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 ...
.
- is upward closed/isotone: If and then for all subsets
* This property entails that (since is a non-empty subset of ).
Given a set
a canonical partial ordering
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 ...
by subset inclusion, turning
into a lattice.
A "dual ideal" is just a filter with respect to this partial ordering.
Note that if
then there is exactly one dual ideal on
which is
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
is a dual ideal on
Equivalently, a filter on
is just a filter with respect the canonical partial ordering
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
is a dual ideal on
with the following additional property:
-
is proper
/non-degenerate: The empty set is not in (i.e. ).
:Note: This article does require that a filter be proper.
The only non-proper filter on
is
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
of
is called a prefilter, filter base, or filter basis if
is non-empty and the intersection of any two members of
is a superset of some member(s) of
If the empty set is not a member of
we say
is a proper filter base.
Given a filter base
the filter generated or spanned by
is defined as the minimum filter containing
It is the family of all those subsets of
which are supersets of some member(s) of
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
of
there is a smallest (possibly non-proper) filter
containing
called the filter generated or spanned by
Similarly as for a filter spanned by a , a filter spanned by a
is the minimum filter containing
It is constructed by taking all finite intersections of
which then form a filter base for
This filter is proper if and only if every finite intersection of elements of
is non-empty, and in that case we say that
is a filter subbase.
Finer/equivalent filter bases
If
and
are two filter bases on
one says
is than
(or that
is a of
) if for each
there is a
such that
For filter bases
and
if
is finer than
and
is finer than
then
is finer than
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
is finer than
one says that they are equivalent filter bases.
If
and
are filter bases, then
is finer than
if and only if the filter spanned by
contains the filter spanned by
Therefore,
and
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
A filter base of tails can be made of any
net using the construction
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
be a set and
be a non-empty subset of
Then
is a filter base. The filter it generates (that is, the collection of all subsets containing
) is called the principal filter generated by
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
is the set of all subsets of
that have finite complement. A filter on
is free if and only if it includes the Fréchet filter.
More generally, if
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
the collection of all
such that
forms a filter. The Fréchet filter is the case where
and
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
is a filter on
Filters in model theory
For every filter
on a set
the set function defined by
is finitely additive — a "
measure" if that term is construed rather loosely. Therefore, the statement
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 ) 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 ...
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
(and its subsets) whereas sequences and nets rely on directed sets that may be unrelated to
Moreover, the set of all filters on
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
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
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
in a topological space
This means that
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
It can be verified that
is a filter. A neighbourhood system is another name for a neighbourhood filter.
A family
of neighbourhoods of
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
if
generates the filter
This means that each subset
of
is a neighbourhood of
if and only if there exists
such that
Convergent filters and cluster points
We say that a filter base
converges to a point
written
if the neighbourhood filter
is contained in the filter
generated by
that is, if
is
finer than
In particular, a filter
(which is a filter base that generates itself) converges to
if
Explicitly, to say that a filter base
converges to
means that for every neighbourhood
of
there is a
such that
If a filter base
converges to a point
then
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
and
is called a
convergent filter base.
A filter base
on
is said to cluster at
(or have
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
has non-empty intersection with each neighbourhood of
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 ...
at a given point
generates
so
converges to
If
is a filter base on
then
if
is
finer than any neighbourhood base at
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