Filter (set theory)

A filter $\mathcal{F}$ on a set $X$ is a nonempty family of subsets that excludes the empty set, is closed under finite intersections, and is upward closed under inclusion.

For a function $f:X\to Y$, the pushforward of a filter on a set $X$ consists of the subsets $B\subseteq Y$ with $f^{-1}(B)\in \mathcal{F}$. Preimages preserve inclusions and finite intersections, so this is a proper filter. Equivalently it is generated by $f(A)$ for $A\in \mathcal{F}$. Because preimages preserve complements too, the pushforward of an ultrafilter is an ultrafilter.

A filter on a set equipped with a topology converges to $x$ if it contains every neighbourhood of $x$. A Hausdorff space gives every convergent filter at most one limit: disjoint neighbourhoods of distinct purported limits would have empty intersection in the filter.

For proper filters on positive integers, define $A\in \mathcal{F}+\mathcal{G}$ when $\{x:A-x\in \mathcal{G}\}\in \mathcal{F}$. This is again a proper filter. The inner truth-set map preserves the whole set, the empty set, inclusions and finite intersections; applying the outer filter gives all filter axioms. The order of the two filter quantifiers is part of the definition and is not silently interchangeable.

For a proper filter on a set, write ${\forall }_{\mathcal{F}}xp(x)$ when the truth set $\{x:p(x)\}$ belongs to the filter. This quantifier preserves finite conjunctions. For an ultrafilter it also preserves finite disjunctions and obeys classical negation; a general proper filter need not have those latter properties.

The even and odd integers are both absent from the cofinite filter, but their union is present. Thus its filter quantifier need not turn a disjunction into the disjunction of quantified assertions, and failure of a quantified assertion need not imply truth of its quantified negation. An ultrafilter restores both laws by deciding each set against its complement.

The filter quantifier satisfies ${\forall }_{\mathcal{F}}(p\wedge q)$ if and only if both ${\forall }_{\mathcal{F}}p$ and ${\forall }_{\mathcal{F}}q$. Finite-intersection closure gives one direction and upward closure gives the other. Properness ensures contradictory truth sets cannot both be filter members.

A free filter on a set $I$ has empty intersection of all its members. This is equivalent to containing every cofinite subset of $I$: for each $i$ some filter member omits $i$, so upward closure gives $I\setminus \{i\}$, and finite intersections give every cofinite set. A proper free filter on an infinite set contains no finite set.

For a free filter $F$, a subset $S$ belongs to $F$ if and only if every ultrafilter extending $F$ contains $S$. If $S\notin F$, every $A\in F$ meets $I\setminus S$ in an infinite set; otherwise a cofinite restriction of $A$ would be contained in $S$. Adjoining $I\setminus S$ therefore generates a proper free filter. The ultrafilter lemma extends it to a nonprincipal ultrafilter witnessing failure of membership.

A filter is $\kappa$-complete when the intersection of every family of fewer than $\kappa$ members again belongs to the filter.

The cobounded filter on a regular cardinal $\kappa$ consists of sets whose complements have cardinality below $\kappa$. Regularity makes it $\kappa$-complete.

The cofinite filter on an infinite set consists of all subsets whose complements are finite.

A subset $E$ of a set $X$ is cofinite in $X$ when its complement $X\setminus E$ is a finite set. For infinite $X$, the cofinite subsets form the cofinite filter. A nonprincipal ultrafilter on $\mathbb{N}$ contains every cofinite subset: it contains no singleton, hence no finite set, and decides between each set and its complement.

Every proper filter on a set is contained in an ultrafilter. Order its proper filter extensions by inclusion, use Zorn lemma to obtain a maximal extension, and observe that maximality forces it to contain exactly one of every set and its complement.

Let $S$ be a nonempty set and $\mathcal{P}\subseteq \mathcal{P}(S)$ be upward closed. An ultrafilter all of whose members lie in $\mathcal{P}$ exists exactly when every finite set partition of $S$ has a cell in $\mathcal{P}$. For sufficiency, the complements of sets outside $\mathcal{P}$ have the finite intersection property: a finite cover by such sets could be disjointified into a partition with no cell in $\mathcal{P}$. The ultrafilter lemma extends the generated proper filter. Necessity follows because an ultrafilter selects exactly one cell of every finite partition. This criterion requires partition richness of the whole ground set; it does not assert that the complement family is closed under unions.

An ultrafilter on a set $X$ is a proper filter on a set that contains exactly one of $A$ and $X\setminus A$ for every $A\subseteq X$.

An ultrafilter on $P_{\kappa }(\lambda )$ is fine when it contains the set of small subsets containing $\alpha$, for each $\alpha <\lambda$. Fineness makes every coordinate of $\lambda$ represented in the corresponding ultrapower, though no one small subset is required to contain every coordinate.

An ultrafilter $U$ on $P_{\kappa }(\lambda )$ is normal when each function with $f(x)\in x$ on a $U$-large set is constant on a $U$-large subset. This is the small-subset version of normality; together with fineness and kappa-completeness it gives the measure characterization of a supercompact cardinal.

A uniform kappa-complete ultrafilter $U$ on an uncountable cardinal $\kappa$ is normal if every regressive function on a $U$-large set is constant on a $U$-large subset. Equivalently it is closed under diagonal intersections ${\Delta }_{\alpha <\kappa }{X}_{\alpha }=\{\beta <\kappa :(\forall \alpha <\beta )\beta \in X_{\alpha }\}$. Normality supplies homogeneous sets for pair-colourings by combining the chosen large tail at each earlier coordinate.

An ultrafilter on the positive integers with every member containing finite arithmetic progressions of arbitrarily large length. The Van der Waerden theorem and ultrafilter selection from a partition-rich family give existence. Such an ultrafilter must contain the complement of every set with bounded arithmetic-progression length, and it is a nonprincipal ultrafilter. No corresponding ultrafilter can have an infinite arithmetic progression in every member, by the dyadic block obstruction to infinite arithmetic progressions.

An ultrafilter with finite-sums members is an ultrafilter on the positive integers all of whose members are IP sets. Such an ultrafilter exists by extending the IP-star filter using the ultrafilter lemma. If a member were not IP, its complement would be an IP-star set and hence another member, contradicting properness. Conversely, every such ultrafilter contains the entire IP-star filter, since it cannot contain the non-IP complement of an IP-star set. This characterization does not assert that the ultrafilter is idempotent.

The finite-trace independent family construction gives $2^{|X|}$ independent subsets of an infinite $X$. Each binary assignment generates a proper filter and, in ZFC, has an ultrafilter extension. Different assignments force incompatible membership decisions, giving $2^{2^{|X|}}$ distinct ultrafilters. The matching upper bound follows because every ultrafilter is a subset of $\mathcal{P}(X)$.

For an ultrafilter $U$ on $X$ and a function $g:X\to Y$, define $g_{\ast }U=\{B\subseteq Y:g^{-1}[B]\in U\}$. This is an ultrafilter and inherits countable completeness from a countably complete ultrafilter. It is nonprincipal exactly when no single fibre of $g$ belongs to $U$. Restricting $U$ to a member of $U$ before pushing forward preserves these properties.

For ultrafilters $\mathcal{U}$ on $I$ and $\mathcal{V}$ on $J$, putThis is an ultrafilter on $I\times J$: upward closure and finite intersection follow at both levels, and the ultrafilter dichotomy follows by complementing at both levels. Iterating gives ordered finite products. Projection onto a subsequence of coordinates pushes this product to the product on that subsequence, since omitted coordinates are absent from the tested first-order formula. The order of coordinates matters; these products need not be symmetric.

The ultrafilter functor sends a set $A$ to its set $\mathcal{U}(A)$ of ultrafilters. A function $f:A\to B$ acts by pushforward,It preserves finite coproducts: an ultrafilter on $A\bigsqcup B$ contains exactly one summand and is uniquely induced by an ultrafilter on that summand.

The ultrafilter functor is terminal among endofunctors of $\mathbf{Set}$ that preserve finite coproducts. For such an endofunctor $F$ and $x\in F(A)$, the unique natural map sends $x$ to

The principal ultrafilter at $x\in X$ is $\{A\subseteq X:x\in A\}$. An ultraproduct by a principal ultrafilter is isomorphic to the factor indexed by $x$.

A nonprincipal ultrafilter contains no finite set. On an infinite set it contains the cofinite filter.

If $U$ is a nonprincipal $\kappa$-complete ultrafilter on $X$ and $A\subseteq X$ has cardinality below $\kappa$, then $A\notin U$. Indeed, every $X\setminus \{a\}$ belongs to $U$, so $\kappa$-completeness puts their intersection $X\setminus A$ in $U$.

An ultrafilter is countably complete when the intersection of every countable family of its members again belongs to it. Equivalently, whenever the underlying set is partitioned into countably many pieces, exactly one piece belongs to the ultrafilter.

The Stone-Cech compactification $\beta \mathbb{N}$ can be identified with the space of ultrafilters on $\mathbb{N}$. Its basic clopen sets are $\bar{A}=\{\mathcal{U}:A\in \mathcal{U}\}$.

This is the natural-number-space case of Stone-Čech compactification.

Every convergent sequence in the Stone-Čech compactification of the natural numbers is eventually constant. If distinct ultrafilters $U_n$ converged, isolate each from the other sequence terms using convergence and finitely many separating clopen sets. Finite disjointification gives disjoint $B_n\in U_n$. The union of the even-indexed $B_n$ then belongs exactly to the even-indexed ultrafilters, contradicting convergence of membership in a clopen set.

For $A\subseteq \mathbb{N}$, the basic set $\hat{A}=\{U:A\in U\}$ in the Stone-Čech compactification of the natural numbers is a clopen set, since its complement is $\widehat{\mathbb{N}\setminus A}$. Distinct ultrafilters are separated by complementary basic sets. A basic cover with no finite subcover would give complements with the finite intersection property, whose generated filter on a set extends to an ultrafilter missing the entire cover. Thus the space is a compact Hausdorff space.

For ultrafilters $\mathcal{U},\mathcal{V}\in \beta \mathbb{N}$, define $\mathcal{U}+\mathcal{V}$ byThis operation is associative, and each right translation $\mathcal{U}\mapsto \mathcal{U}+\mathcal{V}$ is continuous, so $\beta \mathbb{N}$ is a compact Hausdorff left-topological semigroup.

An additive idempotent ultrafilter satisfies $\mathcal{U}+\mathcal{U}=\mathcal{U}$. On positive integers it is necessarily nonprincipal, since a principal ultrafilter at $n$ adds to itself to give the principal ultrafilter at $2n$. The idempotent-ultrafilter star-set lemma converts this algebraic property into a recursive construction of finite sums. If zero is included, the trivial principal idempotent at zero must be excluded for that increasing-sequence application.

For a sequence of positive integers, the nested closures of its tail finite-sums sets have nonempty compact intersection in the Stone-Čech compactification of the natural numbers. This intersection is a subsemigroup. For a sum $s$ from one tail, all sums supported beyond a chosen finite representation of $s$ lie in that tail translated by $-s$. The ultrafilter addition formula then establishes closure under addition. The Ellis–Numakura lemma supplies an idempotent ultrafilter containing every tail finite-sums set and hence any set containing the full finite-sums set.

An ultrafilter on the positive integers selects exactly one residue class modulo a fixed positive integer $q$. Under addition on the Stone-Čech compactification of the natural numbers, selected residues add. An idempotent ultrafilter must therefore select a residue $r$ with $2r=r$ in the finite cyclic group, hence $r=0$. In particular, the multiples of every fixed positive integer belong to every additive idempotent ultrafilter.

For $A\in \mathcal{U}$ and an idempotent ultrafilter, put $A^{\ast }=\{n\in A:A-n\in \mathcal{U}\}$. Then $A^{\ast }\in \mathcal{U}$, and $A^{\ast }-n\in \mathcal{U}$ for every $n\in A^{\ast }$. For the second assertion, apply idempotence to $A-n$ and intersect its resulting good-translation set with $A-n$. This allows each new finite-sums generator to be chosen from finitely many translation constraints, proving the Idempotent-ultrafilter proof of Hindman's theorem.

An ultrafilter $\mathcal{U}\in \beta \mathbb{N}$ is idempotent when $\mathcal{U}+\mathcal{U}=\mathcal{U}$. The Ellis–Numakura lemma guarantees such an ultrafilter and supplies the main algebraic input to the Idempotent-ultrafilter proof of Hindman's theorem.

A point $x$ is the limit of a map $f:I\to X$ along an ultrafilter $\mathcal{U}$ on $I$ when $f^{-1}(V)\in \mathcal{U}$ for every neighbourhood $V$ of $x$. Every ultrafilter on a compact space has a limit, and that limit is unique in a Hausdorff space.

A topological space is both a compact space and a Hausdorff space exactly when every ultrafilter on its underlying set converges to exactly one point. Existence of all ultrafilter limits characterizes compactness. If a space is not Hausdorff, two distinct points have neighbourhood systems whose combined finite intersections are nonempty; the ultrafilter lemma extends these to an ultrafilter converging to both points. Conversely, disjoint neighbourhoods prevent such a common limit.