Given a lattice (L,∧,∨,≤)(L,\wedge,\vee,\leq), a filter on LL is a nonempty set F⊆LF\subseteq L where

  1. ∀x∈F,∀y∈L, x≤y⇒y∈F\forall x\in F, \forall y\in L,\ x\leq y\Rightarrow y\in F
  2. ∀x,y∈F⇒x∧y∈F\forall x,y\in F\Rightarrow x\wedge y\in F

A set satisfying the first condition is called an upper set, while a set satisfying the second is downward-directed. Upper sets are sometimes called filters in the literature, as in Stanley’s Enumerative Combinatorics (p. 282), but upper sets and filters are distinct and have different applications. For instance, Birkhoff’s theorem is a statement about upper sets which is not true if you require them to be filters.

The given definition is motivated by algebra: the filter has a dual known as an ideal, given by switching ≤,∧\leq,\wedge to ≥,∨\geq,\vee. The second property buys you some symmetry with the concept of an ideal in ring theory.

A filter is called proper if it is not the entire set. For the most part we will be dealing with filters on the lattice of subsets of a set XX, written as (P(X),∩,∪,⊆)(\P(X),\cap,\cup,\subseteq).

If CC is a chain of proper filters on P(X)\P(X), then ⋃c∈Cc\displaystyle\bigcup_{c\in C}c is a proper filter.

If Y,Z∈⋃cY,Z\in\bigcup c, then there are filters Y∈FY,Z∈FZY\in F_Y, Z\in F_Z in CC. CC is totally ordered, so we can say without loss of generality that FY⊆FZF_Y\subseteq F_Z. Y,Z∈FZY,Z\in F_Z and Y∩Z∈FZY\cap Z\in F_Z, so Y∩Z∈⋃cY\cap Z\in\bigcup c.

If Y∈⋃cY\in\bigcup c, Z∈P(X)Z\in\P(X), and Y⊆ZY\subseteq Z, then FYF_Y contains both YY and ZZ. Therefore Z∈⋃cZ\in\bigcup c.
If ⋃c\bigcup c is not proper, then ∅∈⋃c\emptyset\in\bigcup c and ∅∈c\emptyset\in c for some c∈Cc\in C. This cannot be the case as all cc are proper. Thus, ⋃c\bigcup c is a proper filter.

An ultrafilter  U⊆L\ \mathcal{U}\subseteq L is a maximal proper filter on LL. That is, if FF is a filter and U⊆F\mathcal{U}\subseteq F, then either U=F\mathcal{U}=F or F=LF=L.

Not every lattice will have an ultrafilter; (Z,min,max,≤)(\Z,\min,\max,\leq) has many filters but no ultrafilters.

Every proper filter in P(X)\P(X) is contained in an ultrafilter.

Let FF be such a filter and Ω\Omega the set of proper filters on P(X)\P(X). Consider F={Y∈Ω:F⊆Y}\mathcal{F}=\{Y\in\Omega: F\subseteq Y\}, the set of filters which extend FF, as the partial order (F,⊆)(\mathcal{F}, \subseteq). If C⊆FC\subseteq\mathcal{F} is a chain of filters, we know ∪c∈Cc\cup_{c\in C}c is a filter, and it is an upper bound for the chain. Since all chains are bounded, F\mathcal{F} must have a maximal element. Thus, there is some maximal filter U⊇F\mathcal{U}\supseteq F.

This statement is usually called the ultrafilter lemma. We proved it with Zorn’s lemma, but it is actually equivalent to the weaker boolean prime ideal theorem. That means there are models of set theory where the ultrafilter lemma is true but Zorn’s lemma is false.

Now we’ll prove an important property of ultrafilters. Let us use BcB^c to denote the set complement X∖BX\setminus B.

If  U⊂P(X)\ \mathcal{U}\subset\P(X) is an ultrafilter, then ∀B∈P(X)\forall B\in\P(X) either B∈UB\in \mathcal{U} or Bc∈UB^c\in \mathcal{U}.

Suppose that B,Bc∈UB,B^c\in \mathcal{U}. Then, B∩Bc=∅∈UB\cap B^c=\emptyset\in \mathcal{U}, which cannot be the case as U\mathcal{U} is a proper filter.

Now, assume B∉UB\notin \mathcal{U} and define U+=U∪{Y⊆X:∃u∈U, Y⊇u∩Bc}\mathcal{U}^+=\mathcal{U}\cup\{Y\subseteq X: \exists u\in \mathcal{U},\ Y\supseteq u\cap B^c\}. If Y∈U+Y\in \mathcal{U}^+, we know Y∈UY\in \mathcal{U} or Y⊇u∩BcY\supseteq u\cap B^c for some u∈Uu\in \mathcal{U}.

Let Y^∈P(X)\hat{Y}\in\P(X) with Y⊆Y^Y\subseteq\hat{Y}; if Y∈UY\in \mathcal{U} then Y^∈U\hat{Y}\in \mathcal{U} as U\mathcal{U} is a filter. Otherwise, u∩Bc⊆Y⊆Y^u\cap B^c\subseteq Y\subseteq\hat{Y}, so Y^∈U+\hat{Y}\in \mathcal{U}^+ as a superset of some u∩Bcu\cap B^c.

Let Y,Z∈U+Y,Z\in \mathcal{U}^+; if both are in U\mathcal{U}, then Y∩Z∈UY\cap Z\in \mathcal{U}. If both are not, then we have u∩Bc⊆Y, v∩Bc⊆Zu\cap B^c\subseteq Y,\ v\cap B^c\subseteq Z for some u,v∈Uu,v\in \mathcal{U}. Then (u∩v)∩Bc(u\cap v)\cap B^c is a lower bound for Y,ZY,Z and so (u∩v)∩Bc⊆Y∩Z(u\cap v)\cap B^c\subseteq Y\cap Z. u∩v∈Uu\cap v\in \mathcal{U} by downward-directedness, so Y∩Z∈U+Y\cap Z\in \mathcal{U}^+. If Y∈U, Z⊇v∩BcY\in \mathcal{U},\ Z\supseteq v\cap B^c, then (Y∩v)∩Bc⊆Y∩Z∈U+(Y\cap v)\cap B^c\subseteq Y\cap Z\in \mathcal{U}^+. Thus, U+\mathcal{U}^+ is a filter.

Moreover, if ∅∈U+\emptyset\in \mathcal{U}^+ then u∩Bc⊆∅u\cap B^c\subseteq\emptyset for some u∈Uu\in \mathcal{U}. This means that u⊆Bu\subseteq B and thus B∈UB\in \mathcal{U}, contradicting our initial assumption. So U+\mathcal{U}^+ is a proper filter which extends U\mathcal{U}, and it must be the case that U=U+\mathcal{U}=\mathcal{U}^+. Since (u∩Bc)⊆Bc(u\cap B^c)\subseteq B^c, we know Bc∈UB^c\in \mathcal{U}.

An ultrafilter is called principal if it is of the form Uα={x∈L:α≤x}\mathcal{U}_\alpha=\{x\in L: \alpha\leq x\} for some α∈L\alpha\in L.

If Uα⊂P(X)\mathcal{U}_\alpha \subset\P(X) is a principal ultrafilter, then α={a}\alpha=\{a\} for some a∈Xa\in X.

Let a∈αa\in\alpha; either {a}\{a\} or X∖{a}X\setminus\{a\} are in U\mathcal{U} by the previous theorem. α⊈X∖{a}\alpha\nsubseteq X\setminus\{a\} by construction, so {a}∈U\{a\}\in\mathcal{U}. Thus, α={a}\alpha=\{a\} as α\alpha cannot be the empty set.

In a finite lattice, all ultrafilters are principal. In an infinite lattice we may find ultrafilters that are not based on a single element. These ultrafilters are called non-principal.

If ∣X∣|X| is infinite, then there exists a non-principal ultrafilter on P(X)\P(X).

Let B={A⊂X:Ac finite}B=\{A\subset X: A^c\ \text{finite}\}. If Y∈BY\in B, Y⊆Y^Y\subseteq\hat{Y}, then Y^c⊆Yc\hat{Y}^c\subseteq Y^c, so Y^c\hat{Y}^c is finite and Y^∈B\hat{Y}\in B. Any Y,Z∈BY,Z\in B have Y∩Z=(X∖Yc)∩(X∖Zc)=X∖(Yc∪Zc)Y\cap Z=(X\setminus Y^c)\cap(X\setminus Z^c)=X\setminus(Y^c\cup Z^c) by De Morgan's law, so Y∩ZY\cap Z has finite complement Yc∪ZcY^c\cup Z^c and Y∩Z∈BY\cap Z\in B.

Thus, BB is a filter and is contained in some ultrafilter AA. Any finite set ZZ has Zc∈AZ^c\in A, so Z∉AZ\notin A. Therefore AA cannot be principal, as it does not contain {a}\{a\} for any a∈Xa\in X.

By this construction, we can see what non-principal ultrafilters look like intuitively. They are filters of co-finite sets and have no minimal element.

Ultrafilters have some interesting applications; in topology, the compactification of the naturals βN\beta\N is a topology generated by ultrafilters on N\N. The elements of N\N are mapped to the principal ultrafilters, and the non-principal ultrafilters are the sets added to make the space compact. Ultrafilters have interesting properties in logic, including the aforementioned relationship to the axiom of choice, and are also studied for their own sake as lattice objects.

Another interesting fact is that you can prove the infinite Ramsey’s theorem using ultrafilters.

Let χ:N2→[r]\chi:\N^2\rightarrow [r] be an infinite rr-coloring of pairs of natural numbers. Then, there is an infinite A⊆NA\subseteq\N where ∣χ(A2)∣=1|\chi(A^2)|=1.

You can see how this theorem is analogous to the finite Ramsey if you think of N2\N^2 as representing the edges of a complete graph on countably many vertices.

Fix a non-principal ultrafilter μ⊂P(N2)\mu\subset\P(\N^2), and define the mapping χ′:N→[r]\chi':\N\rightarrow [r] as χ′(x)=i\chi'(x)=i where {y:X(x,y)=i}∈μ\{y:X(x,y)=i\}\in\mu. That is, the image of xx under χ′\chi' is the color ii where the set of all y∈Ny\in\N connected to xx by an ii-colored edge is in the ultrafilter μ\mu.

We must show χ′\chi' is well-defined. xx is connected to every element of N∖{x}\N\setminus\{x\} by a colored edge, so the set is partitioned into rr parts based on those colors. If two of those partitions A,BA,B are in μ\mu, then A∩B∈μA\cap B\in\mu. However, we know A∩B=∅A\cap B=\emptyset because they are parts of a partition, and ∅∈μ\emptyset\in\mu contradicts the fact that μ\mu must be a proper filter. Thus, there can be only one such set and χ′(x)=i\chi'(x)=i is unique.

χ′\chi' partitions N\N into rr parts by its image. There must be a unique ii such that B={x∈N:χ′(x)=i}B=\{x\in\N: \chi'(x)=i\} and B∈μB\in\mu; if not, we can derive a contradiction as before. Moreover, BB is a set where each x∈Bx\in B has a set of neighbors on ii-colored edges included in the ultrafilter. μ\mu is non-principal, so BB must be infinite. We will use induction to prove that there exists a set A={ai:i∈N}A=\{a_i: i\in\N\} where χ(an,ak)=i\chi(a_n,a_k)=i for all n,kn,k. Select some a1∈Ba_1\in B and assume that the property holds for {a1,…an}\{a_1,\ldots a_n\}.

Define Sn=B∩(⋂j=1n{y∈N:χ(aj,y)=i})S_n=B\cap(\bigcap_{j=1}^n\{y\in\N: \chi(a_j,y)=i\}) We want to pick an+1a_{n+1} from SnS_n, so we must show it is nonempty and contains elements other than {a1,…,an}\{a_1,\ldots, a_n\}. We know by the selection of ii that {y∈N:χ(aj,y)=i}∈μ\{y\in\N: \chi(a_j,y)=i\}\in\mu, because aj∈Ba_j\in B and thus χ′(aj)=i\chi'(a_j)=i. SnS_n is a finite intersection of sets in μ\mu, so Sn∈μS_n\in\mu. By non-principality of μ\mu, we then know that SnS_n is infinite. So, Sn≠∅S_n\neq\emptyset and a1,…,an⊊Sn{a_1,\ldots, a_n}\subsetneq S_n.

Therefore, we can choose an+1∉{a1,…,an}a_{n+1}\notin\{a_1,\ldots, a_n\} from SnS_n, and {a1,…,an+1}\{a_1,\ldots, a_{n+1}\} is monochromatic. By induction, we can construct an infinite monochromatic set A⊆NA\subseteq\N.