Filter (set theory) explained

In mathematics, a filter on a set

X is a family l{B} of subsets such that: X \in l{B} and \emptyset \notin l{B}

1. if

A\in l{B} and B \in l{B} , then A\cap B\in l{B}

1. If

A\subset B\subset X and A\in l{B} , then B\in l{B}

A filter on a set may be thought of as representing a "collection of large subsets", one intuitive example being the neighborhood filter. Filters appear in order theory, model theory, and set theory, but can also be found in topology, from which they originate. The dual notion of a filter is an ideal.

Filters were introduced by Henri Cartan in 1937 and as described in the article dedicated to filters in topology, they were subsequently used by Nicolas Bourbaki in their book Topologie Générale as an alternative to the related notion of a net developed in 1922 by E. H. Moore and Herman L. Smith. Order filters are generalizations of filters from sets to arbitrary partially ordered sets. Specifically, a filter on a set is just a proper order filter in the special case where the partially ordered set consists of the power set ordered by set inclusion.

Preliminaries, notation, and basic notions

In this article, upper case Roman letters like

S and X denote sets (but not families unless indicated otherwise) and \wp(X) will denote the power set of X. A subset of a power set is called (or simply,) where it is if it is a subset of \wp(X). Families of sets will be denoted by upper case calligraphy letters such as l{B}, l{C}, and l{F}. Whenever these assumptions are needed, then it should be assumed that X is non–empty and that l{B}, l{F}, etc. are families of sets over X.

The terms "prefilter" and "filter base" are synonyms and will be used interchangeably.

Warning about competing definitions and notation

There are unfortunately several terms in the theory of filters that are defined differently by different authors. These include some of the most important terms such as "filter". While different definitions of the same term usually have significant overlap, due to the very technical nature of filters (and point–set topology), these differences in definitions nevertheless often have important consequences. When reading mathematical literature, it is recommended that readers check how the terminology related to filters is defined by the author. For this reason, this article will clearly state all definitions as they are used. Unfortunately, not all notation related to filters is well established and some notation varies greatly across the literature (for example, the notation for the set of all prefilters on a set) so in such cases this article uses whatever notation is most self describing or easily remembered.

The theory of filters and prefilters is well developed and has a plethora of definitions and notations, many of which are now unceremoniously listed to prevent this article from becoming prolix and to allow for the easy look up of notation and definitions. Their important properties are described later.

Sets operations

The or in

X of a family of sets l{B} \subseteq \wp(X) is

and similarly the of

l{B} is l{B} ^{\downarrow} : = \{S \subseteq B ~:~ B \in l{B} \} = c up _{B} } \wp(B).

Notation and Definition	Name
\ker l{B} = c ap _{B} } B	of l{B}
S \setminus l{B} : = \{S \setminus B ~:~ B \in l{B}\} = \{S\} (\setminus) l{B}	where S is a set.
l{B} \ vert _{S} : = \{B \cap S ~:~ B \in l{B}\} = l{B} (\cap) \{S\}	or where S is a set; sometimes denoted by l{B} \cap S
l{B} (\cap) l{C} = \{B \cap C ~:~ B \in l{B} and C \in l{C}\}	(l{B} \cap l{C} will denote the usual intersection)
l{B} (\cup) l{C} = \{B \cup C ~:~ B \in l{B} and C \in l{C}\}	(l{B} \cup l{C} will denote the usual union)
l{B} (\setminus) l{C} = \{B \setminus C ~:~ B \in l{B} and C \in l{C}\}	(l{B} \setminus l{C} will denote the usual set subtraction)
l{B} ^{\#} = l{B} ^{\#} = \{S \subseteq X ~:~ S \cap B ≠ \varnothing forall B \in l{B}\}
\wp(X) = \{S ~:~ S \subseteq X\}	of a set X

Throughout,

f is a map and S is a set.

Notation and Definition	Name
f ^{-1} ( l{B}) = \left\{f ^{-1} (B) ~:~ B \in l{B}\right\}	of l{B} under f ^{-1} , or the of l{B} under f
f ^{-1} (S) = \{x \in \operatorname{domain} f ~:~ f(x) \in S\}	of S under f ^{-1} , or the of S under f
f( l{B}) = \{f(B) ~:~ B \in l{B}\}	of l{B} under f
f(S) = \{f(s) ~:~ s \in S \cap \operatorname{domain} f\}	of S under f
\operatorname{image} f = f(\operatorname{domain} f)	(or range) of f

Nets and their tails

A is a set

I together with a preorder, which will be denoted by \leq (unless explicitly indicated otherwise), that makes (I, \leq) into an ; this means that for all i, j \in I, there exists some k \in I such that i \leq k and j \leq k. For any indices i and j, the notation j \geq i is defined to mean i \leq j while i < j is defined to mean that i \leq j holds but it is true that j \leq i (if \leq is antisymmetric then this is equivalent to i \leq j and i ≠ j ).

A is a map from a non–empty directed set into

X. The notation x _{\bull} = \left(x _{i\right)} _{i} will be used to denote a net with domain I.

Notation and Definition	Name
I _{\geq} = \{j \in I ~:~ j \geq i\}	or where (I, \leq) is a directed set.
x _{\geq} = \left\{x _{j} ~:~ j \geq i and j \in I\right\}	or
\operatorname{Tails}\left(x _{\bull} \right) = \left\{x _{\geq} ~:~ i \in I\right\}	or / of x _{\bull} . Also called the generated by (the tails of) x _{\bull} = \left(x _{i\right)} _{i} . If x _{\bull} is a sequence then \operatorname{Tails}\left(x _{\bull} \right) is also called the .
\operatorname{TailsFilter}\left(x _{\bull} \right) = \operatorname{Tails}\left(x _{\bull} \right) ^{\uparrow}	of/generated by (tails of) x _{\bull} = \left(x _{i\right)} _{i}
f\left(I _{\geq} \right) = \{f(j) ~:~ j \geq i and j \in I\}	or where (I, \leq) is a directed set.

Warning about using strict comparison

If

x _{\bull} = \left(x _{i\right)} _{i} is a net and i \in I then it is possible for the set x _{>} = \left\{x _{j} ~:~ j > i and j \in I \right\}, which is called, to be empty (for example, this happens if i is an upper bound of the directed set I ). In this case, the family \left\{x _{>} ~:~ i \in I \right\} would contain the empty set, which would prevent it from being a prefilter (defined later). This is the (important) reason for defining \operatorname{Tails}\left(x _{\bull} \right) as \left\{x _{\geq} ~:~ i \in I \right\} rather than \left\{x _{>} ~:~ i \in I \right\} or even \left\{x _{>} ~:~ i \in I \right\}\cup \left\{x _{\geq} ~:~ i \in I \right\} and it is for this reason that in general, when dealing with the prefilter of tails of a net, the strict inequality < may not be used interchangeably with the inequality \leq.

Filters and prefilters

See also: Filter (mathematics).

The following is a list of properties that a family

l{B} of sets may possess and they form the defining properties of filters, prefilters, and filter subbases. Whenever it is necessary, it should be assumed that l{B} \subseteq \wp(X).

Many of the properties of

l{B} defined above and below, such as "proper" and "directed downward," do not depend on X, so mentioning the set X is optional when using such terms. Definitions involving being "upward closed in X, " such as that of "filter on X, " do depend on X so the set X should be mentioned if it is not clear from context.

$$\backslash textrm(X)\backslash quad=\backslash quad\; \backslash textrm(X)\; \backslash ,\backslash setminus\backslash ,\; \backslash \backslash quad\backslash subseteq\backslash quad\; \backslash textrm(X)\backslash quad\backslash subseteq\backslash quad\; \backslash textrm(X).$$

There are no prefilters on

X = \varnothing (nor are there any nets valued in \varnothing ), which is why this article, like most authors, will automatically assume without comment that X ≠ \varnothing whenever this assumption is needed.

Basic examples

Named examples

• The singleton set
  l{B} = \{X\} is called the or It is the unique filter on X because it is a subset of every filter on X ; however, it need not be a subset of every prefilter on X.
• The dual ideal
  \wp(X) is also called (despite not actually being a filter). It is the only dual ideal on X that is not a filter on X.
• If
  (X, \tau) is a topological space and x \in X, then the neighborhood filter l{N}(x) at x is a filter on X. By definition, a family l{B} \subseteq \wp(X) is called a (resp. a) at x for (X, \tau) if and only if l{B} is a prefilter (resp. l{B} is a filter subbase) and the filter on X that l{B} generates is equal to the neighborhood filter l{N}(x). The subfamily \tau(x) \subseteq l{N}(x) of open neighborhoods is a filter base for l{N}(x). Both prefilters l{N}(x) and \tau(x) also form a bases for topologies on X, with the topology generated \tau(x) being coarser than \tau. This example immediately generalizes from neighborhoods of points to neighborhoods of non–empty subsets S \subseteq X.

• l{B} is an if l{B} = \operatorname{Tails}\left(x _{\bull} \right) for some sequence x _{\bull} = \left(x _{i\right)} ^{inf ty} ^{i =1} in X.

• l{B} is an or a on X if l{B} is a filter on X generated by some elementary prefilter. The filter of tails generated by a sequence that is not eventually constant is necessarily an ultrafilter. Every principal filter on a countable set is sequential as is every cofinite filter on a countably infinite set. The intersection of finitely many sequential filters is again sequential.
• The set
  l{F} of all cofinite subsets of X (meaning those sets whose complement in X is finite) is proper if and only if l{F} is infinite (or equivalently, X is infinite), in which case l{F} is a filter on X known as the or the on X. If X is finite then l{F} is equal to the dual ideal \wp(X), which is not a filter. If X is infinite then the family \{X \setminus \{x\} ~:~ x \in X\} of complements of singleton sets is a filter subbase that generates the Fréchet filter on X. As with any family of sets over X that contains \{X \setminus \{x\} ~:~ x \in X\}, the kernel of the Fréchet filter on X is the empty set: \ker l{F} = \varnothing.
• The intersection of all elements in any non–empty family
  F \subseteq \operatorname{Filters}(X) is itself a filter on X called the or of F in \operatorname{Filters}(X), which is why it may be denoted by w edge _{l{F} \in F } \mathcal. Said differently, \ker F = c ap _{l{F} \in F } \mathcal \in \operatorname(X). Because every filter on X has \{X\} as a subset, this intersection is never empty. By definition, the infimum is the finest/largest (relative to \subseteq and \leq ) filter contained as a subset of each member of F .
  • If
  l{B} and l{F} are filters then their infimum in \operatorname{Filters}(X) is the filter l{B} (\cup) l{F}. If l{B} and l{F} are prefilters then l{B} (\cup) l{F} is a prefilter that is coarser (with respect to \leq ) than both l{B} and l{F} (that is, l{B} (\cup) l{F} \leq l{B} and l{B} (\cup) l{F} \leq l{F} ); indeed, it is one of the finest such prefilters, meaning that if l{S} is a prefilter such that l{S} \leq l{B} and l{S} \leq l{F} then necessarily l{S} \leq l{B} (\cup) l{F}. More generally, if l{B} and l{F} are non−empty families and if S : = \{ l{S} \subseteq \wp(X) ~:~ l{S} \leq l{B} and l{S} \leq l{F}\} then l{B} (\cup) l{F} \in S and l{B} (\cup) l{F} is a greatest element (with respect to \leq ) of S .
• Let
  \varnothing ≠ F \subseteq \operatorname{DualIdeals}(X) and let \cup F = c up _{l{F} \in F } \mathcal. The or of F in \operatorname{DualIdeals}(X), denoted by v ee _{l{F} \in F } \mathcal, is the smallest (relative to \subseteq ) dual ideal on X containing every element of F as a subset; that is, it is the smallest (relative to \subseteq ) dual ideal on X containing \cup F as a subset. This dual ideal is v ee _{l{F} \in F } \mathcal = \pi\left(\cup \mathbb\right)^, where \pi\left(\cup F \right) : = \left\{F _{1} \cap … \cap F _{n} ~:~ n \in \N andevery F _{i} belongstosome l{F} \in F \right\} is the –system generated by \cup F . As with any non–empty family of sets, \cup F is contained in filter on X if and only if it is a filter subbase, or equivalently, if and only if v ee _{l{F} \in F } \mathcal = \pi\left(\cup \mathbb\right)^ is a filter on X, in which case this family is the smallest (relative to \subseteq ) filter on X containing every element of F as a subset and necessarily F \subseteq \operatorname{Filters}(X).
• Let
  \varnothing ≠ F \subseteq \operatorname{Filters}(X) and let \cup F = c up _{l{F} \in F } \mathcal. The or of F in \operatorname{Filters}(X), denoted by v ee _{l{F} \in F } \mathcal if it exists, is by definition the smallest (relative to \subseteq ) filter on X containing every element of F as a subset. If it exists then necessarily v ee _{l{F} \in F } \mathcal = \pi\left(\cup \mathbb\right)^ (as defined above) and v ee _{l{F} \in F } \mathcal will also be equal to the intersection of all filters on X containing \cup F . This supremum of F in \operatorname{Filters}(X) exists if and only if the dual ideal \pi\left(\cup F \right) ^{\uparrow} is a filter on X. The least upper bound of a family of filters F may fail to be a filter. Indeed, if X contains at least 2 distinct elements then there exist filters l{B} and l{C} on X for which there does exist a filter l{F} on X that contains both l{B} and l{C}. If \cup F is not a filter subbase then the supremum of F in \operatorname{Filters}(X) does not exist and the same is true of its supremum in \operatorname{Prefilters}(X) but their supremum in the set of all dual ideals on X will exist (it being the degenerate filter \wp(X) ).
  • If
  l{B} and l{F} are prefilters (resp. filters on X ) then l{B} (\cap) l{F} is a prefilter (resp. a filter) if and only if it is non–degenerate (or said differently, if and only if l{B} and l{F} mesh), in which case it is coarsest prefilters (resp. coarsest filter) on X (with respect to \leq ) that is finer (with respect to \leq ) than both l{B} and l{F}; this means that if l{S} is any prefilter (resp. any filter) such that l{B} \leq l{S} and l{F} \leq l{S} then necessarily l{B} (\cap) l{F} \leq l{S}, in which case it is denoted by l{B} \vee l{F}.
• Let
  I and X be non−empty sets and for every i \in I let l{D} _{i} be a dual ideal on X. If l{I} is any dual ideal on I then c up _{\Xi} } \;\;\bigcap_ \;\mathcal_i is a dual ideal on X called or .
• The club filter of a regular uncountable cardinal is the filter of all sets containing a club subset of
  \kappa. It is a \kappa -complete filter closed under diagonal intersection.

Other examples

• Let
  X = \{p, 1 , 2 , 3 \} and let l{B} = \{\{p\}, \{p, 1 , 2 \}, \{p, 1 , 3 \}\}, which makes l{B} a prefilter and a filter subbase that is not closed under finite intersections. Because l{B} is a prefilter, the smallest prefilter containing l{B} is l{B}. The –system generated by l{B} is \{\{p, 1 \}\} \cup l{B}. In particular, the smallest prefilter containing the filter subbase l{B} is equal to the set of all finite intersections of sets in l{B}. The filter on X generated by l{B} is l{B} ^{\uparrow} = \{S \subseteq X : p \in S\} = \{\{p\} \cup T ~:~ T \subseteq \{ 1 , 2 , 3 \}\}. All three of l{B}, the –system l{B} generates, and l{B} ^{\uparrow} are examples of fixed, principal, ultra prefilters that are principal at the point p; l{B} ^{\uparrow} is also an ultrafilter on X.
• Let
  (X, \tau) be a topological space, l{B} \subseteq \wp(X), and define \overline{ l{B}} : = \left\{\operatorname{cl} _{X} B ~:~ B \in l{B} \right\}, where l{B} is necessarily finer than \overline{ l{B}}. If l{B} is non–empty (resp. non–degenerate, a filter subbase, a prefilter, closed under finite unions) then the same is true of \overline{ l{B}}. If l{B} is a filter on X then \overline{ l{B}} is a prefilter but not necessarily a filter on X although \left(\overline{ l{B}}\right) ^{\uparrow} is a filter on X equivalent to \overline{ l{B}}.
• The set
  l{B} of all dense open subsets of a (non–empty) topological space X is a proper –system and so also a prefilter. If the space is a Baire space, then the set of all countable intersections of dense open subsets is a –system and a prefilter that is finer than l{B}. If X = \R ^{n} (with 1 \leq n \in \N ) then the set l{B} _{\operatorname{LebFinite} } of all B \in l{B} such that B has finite Lebesgue measure is a proper –system and free prefilter that is also a proper subset of l{B}. The prefilters l{B} _{\operatorname{LebFinite} } and l{B} are equivalent and so generate the same filter on X. The prefilter l{B} _{\operatorname{LebFinite} } is properly contained in, and not equivalent to, the prefilter consisting of all dense subsets of \R. Since X is a Baire space, every countable intersection of sets in l{B} _{\operatorname{LebFinite} } is dense in X (and also comeagre and non–meager) so the set of all countable intersections of elements of l{B} _{\operatorname{LebFinite} } is a prefilter and –system; it is also finer than, and not equivalent to, l{B} _{\operatorname{LebFinite} }.
• A filter subbase with no
  \subseteq - smallest prefilter containing it: In general, if a filter subbase l{S} is not a –system then an intersection S _{1} \cap … \cap S _{n} of n sets from l{S} will usually require a description involving n variables that cannot be reduced down to only two (consider, for instance \pi( l{S}) when l{S} = \{( -inf ty, r) \cup (r, inf ty) ~:~ r \in \R\} ). This example illustrates an atypical class of a filter subbases l{S} _{R} where all sets in both l{S} _{R} and its generated –system can be described as sets of the form B _{r,s} , so that in particular, no more than two variables (specifically, r and s ) are needed to describe the generated –system.

  For all

  r, s \in \R, let $$B\_\; =\; (r,\; 0)\; \backslash cup\; (s,\; \backslash infty),$$where B _{r,s} = B _{min(r,s),s} always holds so no generality is lost by adding the assumption r \leq s. For all real r \leq s and u \leq v, if s or v is non-negative then B _{-r,s} \cap B _{-u,v} = B _{-min(r,u),max(s,v)} . ^[1] For every set R of positive reals, let^[2] $$\backslash mathcal\_R\; :=\; \backslash left\backslash \; =\; \backslash \; \backslash quad\; \backslash text\; \backslash quad\; \backslash mathcal\_R\; :=\; \backslash left\backslash \; =\; \backslash .$$

  Let

  X = \R and suppose \varnothing ≠ R \subseteq ( 0 , inf ty) is not a singleton set. Then l{S} _{R} is a filter subbase but not a prefilter and l{B} _{R} = \pi\left( l{S} _{R\right)} is the –system it generates, so that l{B} ^{\uparrow X} _{R} is the unique smallest filter in X = \R containing l{S} _{R.} However, l{S} ^{\uparrow X} _{R} is a filter on X (nor is it a prefilter because it is not directed downward, although it is a filter subbase) and l{S} ^{\uparrow X} _{R} is a proper subset of the filter l{B} ^{\uparrow X} _{R} . If R, S \subseteq ( 0 , inf ty) are non−empty intervals then the filter subbases l{S} _{R} and l{S} _{S} generate the same filter on X if and only if R = S.

  If

  l{C} is a prefilter satisfying l{S} _{(0,infty)} \subseteq l{C} \subseteq l{B} _{(0,infty)} ^[3] then for any C \in l{C} \setminus l{S} _{(0,infty)} , the family l{C} \setminus \{C\} is also a prefilter satisfying l{S} _{(0,infty)} \subseteq l{C} \setminus \{C\} \subseteq l{B} _{(0,infty)} . This shows that there cannot exist a minimal/least (with respect to \subseteq ) prefilter that both contains l{S} _{(0,infty)} and is a subset of the –system generated by l{S} _{(0,} . This remains true even if the requirement that the prefilter be a subset of l{B} _{(0,infty)} = \pi\left( l{S} _{(0,infty)} \right) is removed; that is, (in sharp contrast to filters) there does exist a minimal/least (with respect to \subseteq ) filter containing the filter subbase l{S} _{(0,infty)} .

Ultrafilters

See main article: Ultrafilter (set theory) and Ultrafilter.

There are many other characterizations of "ultrafilter" and "ultra prefilter," which are listed in the article on ultrafilters. Important properties of ultrafilters are also described in that article.

Any non–degenerate family that has a singleton set as an element is ultra, in which case it will then be an ultra prefilter if and only if it also has the finite intersection property. The trivial filter

\{X\} on X is ultra if and only if X is a singleton set.

The ultrafilter lemma

The following important theorem is due to Alfred Tarski (1930).

A consequence of the ultrafilter lemma is that every filter is equal to the intersection of all ultrafilters containing it.^[4] Assuming the axioms of Zermelo–Fraenkel (ZF), the ultrafilter lemma follows from the Axiom of choice (in particular from Zorn's lemma) but is strictly weaker than it. The ultrafilter lemma implies the Axiom of choice for finite sets. If dealing with Hausdorff spaces, then most basic results (as encountered in introductory courses) in Topology (such as Tychonoff's theorem for compact Hausdorff spaces and the Alexander subbase theorem) and in functional analysis (such as the Hahn–Banach theorem) can be proven using only the ultrafilter lemma; the full strength of the axiom of choice might not be needed.

Kernels

The kernel is useful in classifying properties of prefilters and other families of sets.

If

l{B} \subseteq \wp(X) then for any point x, x \not\in \ker l{B} ifandonlyif X \setminus \{x\} \in l{B} ^{\uparrow} .

Properties of kernels

If

l{B} \subseteq \wp(X) then \ker \left( l{B} ^{\uparrow} \right) = \ker l{B} and this set is also equal to the kernel of the –system that is generated by l{B}. In particular, if l{B} is a filter subbase then the kernels of all of the following sets are equal:

(1)

l{B}, (2) the –system generated by l{B}, and (3) the filter generated by l{B}.

If

f is a map then f(\ker l{B}) \subseteq \ker f( l{B}) and f ^{-1} (\ker l{B}) = \ker f ^{-1} ( l{B}). If l{B} \leq l{C} then \ker l{C} \subseteq \ker l{B} while if l{B} and l{C} are equivalent then \ker l{B} = \ker l{C}. Equivalent families have equal kernels. Two principal families are equivalent if and only if their kernels are equal; that is, if l{B} and l{C} are principal then they are equivalent if and only if \ker l{B} = \ker l{C}.

Classifying families by their kernels

If

l{B} is a principal filter on X then \varnothing ≠ \ker l{B} \in l{B} and $$\backslash mathcal\; =\; \backslash ^\; =\; \backslash \; =\; \backslash wp(X\; \backslash setminus\; \backslash ker\; \backslash mathcal)\; \backslash ,(\backslash cup)\backslash ,\; \backslash$$where \{\ker l{B}\} is also the smallest prefilter that generates l{B}.

Family of examples: For any non–empty

C \subseteq \R, the family l{B} _{C} = \{\R \setminus (r + C) ~:~ r \in \R\} is free but it is a filter subbase if and only if no finite union of the form \left(r _{1} + C\right) \cup … \cup \left(r _{n} + C\right) covers \R, in which case the filter that it generates will also be free. In particular, l{B} _{C} is a filter subbase if C is countable (for example, C = \Q, \Z, the primes), a meager set in \R, a set of finite measure, or a bounded subset of \R. If C is a singleton set then l{B} _{C} is a subbase for the Fréchet filter on \R.

For every filter

l{F} on X there exists a unique pair of dual ideals l{F} ^{*} and l{F} ^{\bull} on X such that l{F} ^{*} is free, l{F} ^{\bull} is principal, and l{F} ^{*} \wedge l{F} ^{\bull} = l{F}, and l{F} ^{*} and l{F} ^{\bull} do not mesh (that is, l{F} ^{*} \vee l{F} ^{\bull} = \wp(X) ). The dual ideal l{F} ^{*} is called of l{F} while l{F} ^{\bull} is called where at least one of these dual ideals is filter. If l{F} is principal then l{F} ^{\bull} : = l{F} and l{F} ^{*} : = \wp(X); otherwise, l{F} ^{\bull} : = \{\ker l{F}\} ^{\uparrow} and l{F} ^{*} : = l{F} \vee \{X \setminus \left(\ker l{F}\right)\} ^{\uparrow} is a free (non–degenerate) filter.

Finite prefilters and finite sets

If a filter subbase

l{B} is finite then it is fixed (that is, not free); this is because \ker l{B} = c ap _{B} } B is a finite intersection and the filter subbase l{B} has the finite intersection property. A finite prefilter is necessarily principal, although it does not have to be closed under finite intersections.

If

X is finite then all of the conclusions above hold for any l{B} \subseteq \wp(X). In particular, on a finite set X, there are no free filter subbases (and so no free prefilters), all prefilters are principal, and all filters on X are principal filters generated by their (non–empty) kernels.

The trivial filter

\{X\} is always a finite filter on X and if X is infinite then it is the only finite filter because a non–trivial finite filter on a set X is possible if and only if X is finite. However, on any infinite set there are non–trivial filter subbases and prefilters that are finite (although they cannot be filters). If X is a singleton set then the trivial filter \{X\} is the only proper subset of \wp(X) and moreover, this set \{X\} is a principal ultra prefilter and any superset l{F} \supseteq l{B} (where l{F} \subseteq \wp(Y) and X \subseteq Y ) with the finite intersection property will also be a principal ultra prefilter (even if Y is infinite).

Characterizing fixed ultra prefilters

If a family of sets

l{B} is fixed (that is, \ker l{B} ≠ \varnothing ) then l{B} is ultra if and only if some element of l{B} is a singleton set, in which case l{B} will necessarily be a prefilter. Every principal prefilter is fixed, so a principal prefilter l{B} is ultra if and only if \ker l{B} is a singleton set.

Every filter on

X that is principal at a single point is an ultrafilter, and if in addition X is finite, then there are no ultrafilters on X other than these.

The next theorem shows that every ultrafilter falls into one of two categories: either it is free or else it is a principal filter generated by a single point.

Finer/coarser, subordination, and meshing

The preorder

\leq that is defined below is of fundamental importance for the use of prefilters (and filters) in topology. For instance, this preorder is used to define the prefilter equivalent of "subsequence", where "l{F} \geq l{C} " can be interpreted as "l{F} is a subsequence of l{C} " (so "subordinate to" is the prefilter equivalent of "subsequence of"). It is also used to define prefilter convergence in a topological space. The definition of l{B} meshes with l{C}, which is closely related to the preorder \leq, is used in Topology to define cluster points.

Two families of sets

l{B} and l{C} and are, indicated by writing l{B} \# l{C}, if B \cap C ≠ \varnothing forall B \in l{B} and C \in l{C}. If l{B} and l{C} do not mesh then they are . If S \subseteq X and l{B} \subseteq \wp(X) then l{B} and S are said to if l{B} and \{S\} mesh, or equivalently, if the of l{B} on S, which is the family$$\backslash mathcal\backslash big\backslash vert\_S\; =\; \backslash ,$$ does not contain the empty set, where the trace is also called the of l{B} to S.

Example: If

x _{i _{\bull}} = \left(x _{i _{n}} \right) ^{inf ty} _{n =1} is a subsequence of x _{\bull} = \left(x _{i\right)} ^{inf ty} ^{i =1} then \operatorname{Tails}\left(x _{i _{\bull}} \right) is subordinate to \operatorname{Tails}\left(x _{\bull} \right); in symbols: \operatorname{Tails}\left(x _{i _{\bull}} \right) \vdash \operatorname{Tails}\left(x _{\bull} \right) and also \operatorname{Tails}\left(x _{\bull} \right) \leq \operatorname{Tails}\left(x _{i _{\bull}} \right). Stated in plain English, the prefilter of tails of a subsequence is always subordinate to that of the original sequence. To see this, let C : = x _{\geq} \in \operatorname{Tails}\left(x _{\bull} \right) be arbitrary (or equivalently, let i \in \N be arbitrary) and it remains to show that this set contains some F : = x _{i _{\geq}} \in \operatorname{Tails}\left(x _{i _{\bull}} \right). For the set x _{\geq} = \left\{x _{i,} x _{i+1} , \ldots\right\} to contain x _{i _{\geq}} = \left\{x _{i _{n}} , x _{i _{n+1}} , \ldots\right\}, it is sufficient to have i \leq i _{n.} Since i _{1} < i _{2} < … are strictly increasing integers, there exists n \in \N such that i _{n} \geq i, and so x _{\geq} \supseteq x _{i _{\geq}} holds, as desired. Consequently, \operatorname{TailsFilter}\left(x _{\bull} \right) \subseteq \operatorname{TailsFilter}\left(x _{i _{\bull}} \right). The left hand side will be a subset of the right hand side if (for instance) every point of x _{\bull} is unique (that is, when x _{\bull} : \N \to X is injective) and x _{i _{\bull}} is the even-indexed subsequence \left(x _{2,} x _{4,} x _{6,} \ldots\right) because under these conditions, every tail x _{i _{\geq}} = \left\{x _{2n} , x _{2n} , x _{2n} , \ldots\right\} (for every n \in \N ) of the subsequence will belong to the right hand side filter but not to the left hand side filter.

For another example, if

l{B} is any family then \varnothing \leq l{B} \leq l{B} \leq \{\varnothing\} always holds and furthermore, \{\varnothing\} \leq l{B} ifandonlyif \varnothing \in l{B}.

Assume that

l{C} and l{F} are families of sets that satisfy l{B} \leq l{F} and l{C} \leq l{F}. Then \ker l{F} \subseteq \ker l{C}, and l{C} ≠ \varnothing implies l{F} ≠ \varnothing, and also \varnothing \in l{C} implies \varnothing \in l{F}. If in addition to l{C} \leq l{F}, l{F} is a filter base and l{C} ≠ \varnothing, then l{C} is a filter subbase and also l{C} and l{F} mesh.^[5] More generally, if both \varnothing ≠ l{B} \leq l{F} and \varnothing ≠ l{C} \leq l{F} and if the intersection of any two elements of l{F} is non–empty, then l{B} and l{C} mesh. Every filter subbase is coarser than both the –system that it generates and the filter that it generates.

If

l{C} and l{F} are families such that l{C} \leq l{F}, the family l{C} is ultra, and \varnothing \not\in l{F}, then l{F} is necessarily ultra. It follows that any family that is equivalent to an ultra family will necessarily ultra. In particular, if l{C} is a prefilter then either both l{C} and the filter l{C} ^{\uparrow} it generates are ultra or neither one is ultra. If a filter subbase is ultra then it is necessarily a prefilter, in which case the filter that it generates will also be ultra. A filter subbase l{B} that is not a prefilter cannot be ultra; but it is nevertheless still possible for the prefilter and filter generated by l{B} to be ultra. If S \subseteq X and l{B} \subseteq \wp(X) is upward closed in X then S \not\in l{B} ifandonlyif (X \setminus S) \# l{B}.

Relational properties of subordination

The relation

\leq is reflexive and transitive, which makes it into a preorder on \wp(\wp(X)). The relation \leq on \operatorname{Filters}(X) is antisymmetric but if X has more than one point then it is symmetric.

For any

l{B} \subseteq \wp(X), l{B} \leq \{X\} ifandonlyif \{X\} = l{B}. So the set X has more than one point if and only if the relation \leq on \operatorname{Filters}(X) is symmetric.

If

l{B} \subseteq l{C} then l{B} \leq l{C} but while the converse does not hold in general, it does hold if l{C} is upward closed (such as if l{C} is a filter). Two filters are equivalent if and only if they are equal, which makes the restriction of \leq to \operatorname{Filters}(X) antisymmetric. But in general, \leq is antisymmetric on \operatorname{Prefilters}(X) nor on \wp(\wp(X)) ; that is, l{C} \leq l{B} and l{B} \leq l{C} does necessarily imply l{B} = l{C} ; not even if both l{C} and l{B} are prefilters. For instance, if l{B} is a prefilter but not a filter then l{B} \leq l{B} ^{\uparrow} and l{B} ^{\uparrow} \leq l{B} but l{B} ≠ l{B} ^{\uparrow} .

Equivalent families of sets

The preorder

\leq induces its canonical equivalence relation on \wp(\wp(X)), where for all l{B}, l{C} \in \wp(\wp(X)), l{B} is to l{C} if any of the following equivalent conditions hold:

1. l{C} \leq l{B} and l{B} \leq l{C}.
2. The upward closures of l{C} and l{B} are equal.

Two upward closed (in

X ) subsets of \wp(X) are equivalent if and only if they are equal. If l{B} \subseteq \wp(X) then necessarily \varnothing \leq l{B} \leq \wp(X) and l{B} is equivalent to l{B} ^{\uparrow} . Every equivalence class other than \{\varnothing\} contains a unique representative (that is, element of the equivalence class) that is upward closed in X.

Properties preserved between equivalent families

Let

l{B}, l{C} \in \wp(\wp(X)) be arbitrary and let l{F} be any family of sets. If l{B} and l{C} are equivalent (which implies that \ker l{B} = \ker l{C} ) then for each of the statements/properties listed below, either it is true of l{B} and l{C} or else it is false of l{B} and l{C} :

1. Not empty
2. Proper (that is, \varnothing is not an element)
   • Moreover, any two degenerate families are necessarily equivalent.

3. Filter subbase
4. Prefilter
   • In which case
   l{B} and l{C} generate the same filter on X (that is, their upward closures in X are equal).
5. Free
6. Principal
7. Ultra
8. Is equal to the trivial filter \{X\}
   • In words, this means that the only subset of
   \wp(X) that is equivalent to the trivial filter the trivial filter. In general, this conclusion of equality does not extend to non−trivial filters (one exception is when both families are filters).
9. Meshes with l{F}
10. Is finer than l{F}
11. Is coarser than l{F}
12. Is equivalent to l{F}

Missing from the above list is the word "filter" because this property is preserved by equivalence. However, if

l{B} and l{C} are filters on X, then they are equivalent if and only if they are equal; this characterization does extend to prefilters.

Equivalence of prefilters and filter subbases

If

l{B} is a prefilter on X then the following families are always equivalent to each other:

1. l{B} ;
2. the –system generated by l{B} ;
3. the filter on X generated by l{B} ;

and moreover, these three families all generate the same filter on X (that is, the upward closures in X of these families are equal).

In particular, every prefilter is equivalent to the filter that it generates. By transitivity, two prefilters are equivalent if and only if they generate the same filter.^[6] Every prefilter is equivalent to exactly one filter on

X, which is the filter that it generates (that is, the prefilter's upward closure). Said differently, every equivalence class of prefilters contains exactly one representative that is a filter. In this way, filters can be considered as just being distinguished elements of these equivalence classes of prefilters.

A filter subbase that is also a prefilter can be equivalent to the prefilter (or filter) that it generates. In contrast, every prefilter is equivalent to the filter that it generates. This is why prefilters can, by and large, be used interchangeably with the filters that they generate while filter subbases cannot. Every filter is both a –system and a ring of sets.

Examples of determining equivalence/non–equivalence

Examples: Let

X = \R and let E be the set \Z of integers (or the set \N ). Define the sets $$\backslash mathcal\; =\; \backslash$$

Notes and References

1. More generally, for any real numbers satisfying r \leq s and u \leq v, B _{r,s} \cap B _{u,v} = B _{m,max(s,v)} where m : = min (s,v, max (r,u)).
2. If R, S \subseteq \R then l{B} _{R} \cap l{B} _{S} = l{B} _{R} . This property and the fact that l{B} _{R} is nonempty and proper if and only if R ≠ \varnothing actually allows for the construction of even more examples of prefilters, because if l{S} \subseteq \wp(\R) is any prefilter (resp. filter subbase, –system) then so is \left\{ l{B} _{S} : S \in l{S}\right\}.
3. It may be shown that if l{C} is any family such that l{S} _{(0,infty)} \subseteq l{C} \subseteq l{B} _{(0,infty)} then l{C} is a prefilter if and only if for all real 0 < r \leq s there exist real 0 < u \leq v such that u \leq r \leq s \leq v and B _{-u,v} \in l{C}.
4. Let l{F} be a filter on X . If S \subseteq X is such that S \not\in l{F} then \{X \setminus S\} \cup l{F} has the finite intersection property (because for all F \in l{F}, F \cap (X \setminus S) = \varnothing ifandonlyif F \subseteq S ). By the ultrafilter lemma, there exists some ultrafilter l{U} _{S} on X such that \{X \setminus S\} \cup l{F} \subseteq l{U} _{S} (so, in particular, S \not\in l{U} _{S} ). Intersecting all such l{U} _{S} proves that l{F} = c ap _{S} } \mathcal_S. \blacksquare
5. To prove that l{B} and l{C} mesh, let B \in l{B} and C \in l{C}. Because l{B} \leq l{F} (resp. because l{C} \leq l{F} ), there exists some F, G \in l{F} suchthat F \subseteq B and G \subseteq C where by assumption F \cap G ≠ \varnothing so \varnothing ≠ G \cap F \subseteq B \cap C. \blacksquare If l{F} is a filter subbase and if \varnothing ≠ l{C} \leq l{F}, then taking l{B} : = l{F} implies that l{C} and l{F} mesh. \blacksquare If C _{1,} \ldots, C _{n} \in l{C} then there are F _{1,} \ldots, F _{n} \in l{F} such that F _{i} \subseteq C _{i} and now \varnothing ≠ F _{1} \cap … F _{n} \subseteq C _{1} \cap … C _{n.} This shows that l{C} is a filter subbase. \blacksquare
6. This is because if l{C} and l{F} are prefilters on X then l{C} \leq l{F} ifandonlyif l{C} ^{\uparrow} \subseteq l{F} ^{\uparrow} .