Filter (mathematics)

The power set lattice of the set

{1, 2, 3, 4}

, with upper set

↑{1, 4}

colored dark green. This upper set is a filter, and even a principal filter. It is not an ultrafilter, because including also the light green elements extends it to the larger nontrivial filter

↑{1}

. Since the latter cannot be extended further,

↑{1}

is an ultrafilter.

In mathematics, a filter or order filter is a special subset of a partially ordered set (poset), describing "large" or "eventual" elements. Filters appear in order and lattice theory, but also topology, whence they originate. The notion dual to a filter is an order ideal.

Special cases of filters include ultrafilters, which are filters that cannot be enlarged, and describe nonconstructive techniques in mathematical logic.

Filters on sets were introduced by Henri Cartan in 1937. Nicolas Bourbaki, in their book Topologie Générale, popularized filters as an alternative to E. H. Moore and Herman L. Smith's 1922 notion of a net; order filters generalize this notion from the specific case of a power set under inclusion to arbitrary partially ordered sets. Nevertheless, the theory of power-set filters retains interest in its own right, in part for substantial applications in topology.

Motivation

Fix a partially ordered set (poset) $P$ . Intuitively, a filter $F$ is a subset of $P$ whose members are elements large enough to satisfy some criterion.^[1] For instance, if $x \in P$ , then the set of elements above $x$ is a filter, called the principal filter at $x$ . (If $x$ and $y$ are incomparable elements of $P$ , then neither the principal filter at $x$ nor $y$ is contained in the other.)

Similarly, a filter on a set $S$ contains those subsets that are sufficiently large to contain some given thing. For example, if $S$ is the real line and $x \in S$ , then the family of sets including $x$ in their interior is a filter, called the neighborhood filter at $x$ . The thing in this case is slightly larger than $x$ , but it still does not contain any other specific point of the line.

The above considerations motivate the upward closure requirement in the definition below: "large enough" objects can always be made larger.

To understand the other two conditions, reverse the roles and instead consider $F$ as a "locating scheme" to find $x$ . In this interpretation, one searches in some space $X$ , and expects $F$ to describe those subsets of $X$ that contain the goal. The goal must be located somewhere; thus the empty set $\emptyset$ can never be in $F$ . And if two subsets both contain the goal, then should "zoom in" to their common region.

An ultrafilter describes a "perfect locating scheme" where each scheme component gives new information (either "look here" or "look elsewhere"). Compactness is the property that "every search is fruitful," or, to put it another way, "every locating scheme ends in a search result."

A common use for a filter is to define properties that are satisfied by "generic" elements of some topological space.^[2] This application generalizes the "locating scheme" to find points that might be hard to write down explicitly.

Definition

A subset $F$ of a partially ordered set $(P, \leq)$ is a filter or dual ideal if:

Nontriviality: The set $F$ is non-empty.
Downward directed: For every $x, y \in F$ , there is some $z \in F$ such that $z \leq x$ and $z \leq y$ .
Upward closure: For every $x \in F$ and $p \in P$ , the condition $x \leq p$ implies $p \in F$ .

If $F \neq P$ as well, then $F$ is said to be a proper filter. Authors in set theory and mathematical logic often require all filters to be proper; this article will eschew that convention.^[3] An ultrafilter is a filter contained in no other proper filter.

Filter bases

A subset $S$ of $F$ is a base or basis for $F$ if the upper set generated by $S$ (i.e., the smallest upwards-closed containing $S$ ) is all of $F$ . Every filter is a base for itself.

Moreover, if $B \subseteq P$ is nonempty and downward directed, then $B$ generates an upper set $F$ that is a filter (for which $B$ is a base). Such sets are called prefilters, as well as the aforementioned filter base/basis, and $F$ is said to be generated or spanned by $B$ . A prefilter is proper if and only if it generates a proper filter.

Given $p \in P$ , the set ${x : p \leq x}$ is the smallest filter containing $p$ , and sometimes written $↑ p$ . Such a filter is called a principal filter; $p$ is said to be the principal element of $F$ , or generate $F$ .

Refinement

Suppose $B$ and $C$ are two prefilters on $P$ , and, for each $c \in C$ , there is a $b \in B$ , such that $b \leq c$ . Then we say that $B$ is finer than (or refines) $C$ ; likewise, $C$ is coarser than (or coarsens) $B$ . Refinement is a preorder on the set of prefilters. In fact, if $C$ also refines $B$ , then $B$ and $C$ are called equivalent, for they generate the same filter. Thus passage from prefilter to filter is an instance of passing from a preordering to associated partial ordering.

Special cases

Historically, filters generalized to order-theoretic lattices before arbitrary partial orders. In the case of lattices, downward direction can be written as closure under finite meets: for all $x, y \in F$ , one has $x \land y \in F$ .^[4]

Linear filters

A linear (ultra)filter is an (ultra)filter on the lattice of vector subspaces of a given vector space, ordered by inclusion. Explicitly, a linear filter on a vector space $X$ is a family $B$ of vector subspaces of $X$ such that if $A, B \in B$ and $C$ is a vector subspace of $X$ that contains $A$ , then $A \cap B \in B$ and $C \in B$ .^[5]

A linear filter is proper if it does not contain ${0}$ .^[5]

Filters on a set; subbases

Families ${\mathcal {F}}$ of sets over $\Omega$ v t e
Is necessarily true of ${\mathcal {F}}\colon$ or, is ${\mathcal {F}}$ closed under:	Directed by $\,\supseteq$	$A\cap B$	$A\cup B$	$B\setminus A$	$\Omega \setminus A$	$A_{1}\cap A_{2}\cap \cdots$	$A_{1}\cup A_{2}\cup \cdots$	$\Omega \in {\mathcal {F}}$	$\varnothing \in {\mathcal {F}}$	F.I.P.
[[pi-system\| $π$ -system]]	Yes	Yes	No	No	No	No	No	No	No	No
Semiring	Yes	Yes	No	No	No	No	No	No	Yes	Never
[[Semialgebra\|Semialgebra (Semifield)]]	Yes	Yes	No	No	No	No	No	No	Yes	Never
[[Monotone class\|Monotone class]]	No	No	No	No	No	only if $A_{i}\searrow$	only if $A_{i}\nearrow$	No	No	No
[[Dynkin system\|𝜆-system (Dynkin System)]]	Yes	No	No	only if $A\subseteq B$	Yes	No	only if $A_{i}\nearrow$ or they are disjoint	Yes	Yes	Never
[[Ring of sets\|Ring (Order theory)]]	Yes	Yes	Yes	No	No	No	No	No	No	No
[[Ring of sets\|Ring (Measure theory)]]	Yes	Yes	Yes	Yes	No	No	No	No	Yes	Never
[[Delta-ring\|δ-Ring]]	Yes	Yes	Yes	Yes	No	Yes	No	No	Yes	Never
[[Sigma-ring\|𝜎-Ring]]	Yes	Yes	Yes	Yes	No	Yes	Yes	No	Yes	Never
[[Field of sets\|Algebra (Field)]]	Yes	Yes	Yes	Yes	Yes	No	No	Yes	Yes	Never
[[σ-algebra\|𝜎-Algebra (𝜎-Field)]]	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Yes	Never
[[Dual ideal\|Dual ideal]]	Yes	Yes	Yes	No	No	No	Yes	Yes	No	No
[[Filter (set theory)\|Filter]]	Yes	Yes	Yes	Never	Never	No	Yes	Yes	$\varnothing \not \in {\mathcal {F}}$	Yes
[[Prefilter\|Prefilter (Filter base)]]	Yes	No	No	Never	Never	No	No	No	$\varnothing \not \in {\mathcal {F}}$	Yes
[[Filter subbase\|Filter subbase]]	No	No	No	Never	Never	No	No	No	$\varnothing \not \in {\mathcal {F}}$	Yes
[[Topology (structure)\|Open Topology]]	Yes	Yes	Yes	No	No	No

[1]

[2]

[3]

[4]

[5]

Anonymous

Search

Filter (mathematics)

Namespaces

More

Page actions

Contents