Filter (math)
In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in topology. The dual notion of an order filter is order ideal.
General definition
A non-empty subset F of a partially ordered set (P,≤) is a filter, if the following conditions hold:
- For every x in F, x ≤ y implies that y is in F. (F is an upper set)
- For every x, y in F, there is some element z in F, such that z ≤ x and z ≤ y. (F is a filtered set)
A filter is proper if it is not equal to the whole set P.
While the above definition is the most general way to define a filter for arbitrary posets, it was originally defined for lattices only. In this case, the above definition can be characterized by the following equivalent statement:
A non-empty subset F of a lattice (P,≤) is a filter, iff it is an upper set that is closed under finite joins (infima), i.e., for all x, y in F, we find that x ∨ y is also in F.
The smallest filter that contains a given element p is a principal filter and p is a principal element in this situation. The principal filter for p is just given by the set {x in P | p ≤ x} and is denoted by prefixing p with an upward arrow.
The dual notion of a filter, i.e. the concept obtained by reversing all ≤ and exchanging ∧ with ∨, is ideal. Because of this duality, the discussion of filters usually boils down to the discussion of ideals. Hence, all additional information on this topic (including the definition of maximal filters, ultrafilters, and prime filters) is to be found in the article on order ideals.
Filters of sets
An important special case of order filters are filters of sets, which are obtained by taking the powerset of a set S as a partial order, ordered by subset inclusion. Thus, a filter F on a set S is a set of subsets of S with the following properties:
- S is in F. (F is non-empty)
- The empty set is not in F. (F is proper)
- If A and B are in F, then so is their intersection. (F is closed under finite joins)
- If A is in F and A ⊆ B ⊆ S, then B is in F. (F is an upper set)
Note that this definition is in absolute correspondence with the general notion introduced above, since the powerset clearly forms a lattice.
A simple example of a filter is the set of all subsets of S that include a particular subset C of S. Such a filter is called the "principal filter" generated by C. The Fréchet filter on an infinite set S is the set of all subsets of S that have finite complement.
Filters are useful in topology: they play the role of sequences in metric spaces. The set of all neighbourhoods of a point x in a topological space is a filter, called the neighbourhood filter of x. A filter which is a superset of the neighbourhood filter of x is said to converge to x. Note that in a non-Hausdorff space a filter can converge to more than one point.
For any filter F on a set S, 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 proofs) in the theory of ultraproducts in model theory, a branch of mathematical logic.
|
