Filter (mathematics)

This article includes a list of general references, but it remains largely unverified because it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (June 2017) (Learn how and when to remove this template message)

The powerset lattice of the set ${\displaystyle \{1,2,3,4\},}$ with the upper set ${\displaystyle \uparrow \{1,4\}}$ colored dark green. It is a filter, and even a principal filter. It is not an ultrafilter, as it can be extended to the larger nontrivial filter ${\displaystyle \uparrow \{1\},}$ by including also the light green elements. Since ${\displaystyle \uparrow \{1\}}$ cannot be extended any further, it is an ultrafilter.

In mathematics, a filter or order filter is a special subset of a partially ordered set. Filters appear in order and lattice theory, but can also be found in topology, from which they originate. The dual notion of a filter is an order 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.

Motivation[]

1. Intuitively, a filter in a partially ordered set (poset), ${\displaystyle P,}$ is a subset of ${\displaystyle P}$ that includes as members those elements that are large enough to satisfy some given criterion. For example, if ${\displaystyle x}$ is an element of the poset, then the set of elements that are above ${\displaystyle x}$ is a filter, called the principal filter at ${\displaystyle x.}$ (If ${\displaystyle x}$ and ${\displaystyle y}$ are incomparable elements of the poset, then neither of the principal filters at ${\displaystyle x}$ and ${\displaystyle 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 thing. For example, if the set is the real line and ${\displaystyle x}$ is one of its points, then the family of sets that include ${\displaystyle x}$ in their interior is a filter, called the filter of neighbourhoods of ${\displaystyle x.}$ The thing in this case is slightly larger than ${\displaystyle 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: 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 common "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 ${\displaystyle X,}$ call a filter the collection of subsets of ${\displaystyle X}$ that might contain "what is looked for". Then this "filter" should possess the following natural structure:

1. A locating scheme must be non-empty in order to be of any use at all.
2. If two subsets, ${\displaystyle E}$ and ${\displaystyle F,}$ both might contain "what is looked for", then so might their intersection. Thus the filter should be closed with respect to finite intersection.
3. If a set ${\displaystyle 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 each subset ${\displaystyle E}$ of the space ${\displaystyle X}$ can be used in deciding whether "what is looked for" might lie in ${\displaystyle 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 and logic.

3. A common use for a filter is to define properties that are satisfied by "almost all" elements of some topological space ${\displaystyle X}$.^[3] The entire space ${\displaystyle X}$ definitely contains almost-all elements in it; If some ${\displaystyle E\subseteq X}$ contains almost all elements of ${\displaystyle X}$, then any superset of it definitely does; and if two subsets, ${\displaystyle E}$ and ${\displaystyle F,}$ contain almost-all elements of ${\displaystyle X}$, then so does their intersection. In a measure-theoretic terms, the meaning of "${\displaystyle E}$ contains almost-all elements of ${\displaystyle X}$" is that the measure of ${\displaystyle X\setminus E}$ is 0.

General definition: Filter on a partially ordered set[]

A subset ${\displaystyle F}$ of a partially ordered set ${\displaystyle (P,\leq )}$ is an order filter if the following conditions hold:

1. ${\displaystyle F}$ is non-empty.
2. ${\displaystyle F}$ is downward directed: For every ${\displaystyle x,y\in F,}$ there is some ${\displaystyle z\in F}$ such that ${\displaystyle z\leq x}$ and ${\displaystyle z\leq y.}$
3. ${\displaystyle F}$ is an upper set or upward-closed: For every ${\displaystyle x\in F}$ and ${\displaystyle p\in P,}$ ${\displaystyle x\leq p}$ implies that ${\displaystyle p\in F.}$

${\displaystyle F}$ is said to be proper if in addition ${\displaystyle F}$ is not equal to the whole set ${\displaystyle P.}$ Depending on the author, the term filter is either a synonym of order filter or else it refers to a proper 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 ${\displaystyle F}$ of a lattice ${\displaystyle (P,\leq )}$ is a filter, if and only if it is a non-empty upper set that is closed under finite infima (or meets), that is, for all ${\displaystyle x,y\in F,}$ it is also the case that ${\displaystyle x\wedge y\in F.}$^[4] A subset ${\displaystyle S}$ of ${\displaystyle F}$ is a filter basis if the upper set generated by ${\displaystyle S}$ is all of ${\displaystyle F.}$ Note that every filter is its own basis.

The smallest filter that contains a given element ${\displaystyle p\in P}$ is a principal filter and ${\displaystyle p}$ is a principal element in this situation. The principal filter for ${\displaystyle p}$ is just given by the set ${\displaystyle \{x\in P:p\leq x\}}$ and is denoted by prefixing ${\displaystyle p}$ with an upward arrow: ${\displaystyle \uparrow p.}$

The dual notion of a filter, that is, the concept obtained by reversing all ${\displaystyle \,\leq \,}$ and exchanging ${\displaystyle \,\wedge \,}$ with ${\displaystyle \,\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 ultrafilters.

Filter on a set[]

Families ${\displaystyle {\mathcal {F}}}$ of sets over ${\displaystyle \Omega }$
Is necessarily true of ${\displaystyle {\mathcal {F}}\colon }$ or, is ${\displaystyle {\mathcal {F}}}$ closed under:	Directed by ${\displaystyle \,\supseteq }$	${\displaystyle A\cap B}$	${\displaystyle A\cup B}$	${\displaystyle B\setminus A}$	${\displaystyle \Omega \setminus A}$	${\displaystyle A_{1}\cap A_{2}\cap \cdots }$	${\displaystyle A_{1}\cup A_{2}\cup \cdots }$	${\displaystyle \Omega \in {\mathcal {F}}}$	${\displaystyle \varnothing \in {\mathcal {F}}}$	F.I.P.
π-system
Semiring										Never
Semialgebra (Semifield)										Never
Monotone class						only if ${\displaystyle A_{i}\searrow }$	only if ${\displaystyle A_{i}\nearrow }$