Franklin's Notes


Filters and ultrafilters

If $P$ is a partially ordered set ordered by $\leq$, a nonempty subset $F\subset P$ is called a filter if any two elements of $F$ have a lower bound in $F$, and if for each element $x\in F$, $F$ contains all elements of $P$ greater than $x$. That is:

1. For all $x,y\in F$, there exists $z\in F$ such that $z\leq x$ and $z\leq y$.
2. For all $x\in F$ and $y\in P$, if $x\leq y$ then $y\in F$.

A filter on a poset can be thought of as a way of drawing a line between the "big" elements and the "small" elements. An ultrafilter $U\subset P$ is a proper filter which is not properly contained in any other proper filter of $P$. A principal filter is one that has a least element $a$, or which takes the form ${x\in P: a\leq x}$. Notice that if $P=2^A$ is the poset of subsets of some set $A$, then the only principal ultrafilters on $P$ are generated by the one-element sets ${x}$ where $x\in A$, since the principal filter generated by $S\subset A$ can always be enlarged to a greater propert filter generated by ${s}\subset S$ for any element $s\in S$, so long as $|S|>1$.

Filters and ultrafilters may also be defined on boolean algebras using their definition of $\leq$. On a boolean algebra, a filter may be thought of as a finitely additive measure. The principal ultrafilters are precisely those taking the form ${x\in B:a\leq x}$ where $a$ is an atom, for if $a$ were not an atom, this filter could be extended to a larger proper filter by replacing $a$ with a nonzero element smaller than $a$.

Ultrafilter Lemma. Every proper filter $F$ of a poset $P$ is contained in an ultrafilter $F\subset U\subset P$.

Proof. This result may be proven using Zorn's Lemma . Consider the poset of filters containing $F$, ordered by inclusion. This poset is nontrivial unless $F$ is already an ultrafilter, in which case our result follows trivially. Given a chain of nested filters containing $F$, their union is a filter containing $F$ and each of the filters in the chain; hence, every chain in this poset has an upper bound. Thus, by Zorn's Lemma, there exists a maximal filter containing $F$, or an ultrafilter $U$ containing $F$. $\blacksquare$

This theorem is strictly weaker than Zorn's Lemma and the Axiom of Choice . (Although, I'm not sure how to prove this yet...)

Proposition 1. If $U$ is an ultrafilter on a boolean algebra , for any two elements $x,y$ of that boolean algebra, we have that $x\in U$ if and only if $\overline{x}\notin U$, and $x+y\in U$ if and only if either $x\in U$ or $y\in U$.

Proof. Clearly $x,\overline{x}$ cannot both be in the same proper filter, for this would imply that the filter contained $x\cdot\overline{x}=0$. On the other hand, suppose that neither $x$ nor $\overline{x}$ is contained in $U$ for some element $x$ (we ignore the cases of $x=0$ and $x=1$, since they are trivial). Then consider the set This set is also a filter: for if $u'_1 = u_1\cdot z_1$ and $u'_2=u_2\cdot z_2$, then $u'_1\cdot u'_2 = (u_1\cdot u_2)\cdot (z_1\cdot z_2)\in U'$, meaning that property $(1)$ of filters is satisfied; and if $u'=u\cdot z + w$ for some $w$, then $u'=(u+w)\cdot (z+w)\in U'$, meaning that property $(2)$ of filters is satisfied. But $\overline{x}\notin U'$, meaning that $U'$ is a proper filter extending $U$, contradicting the fact that $U$ is an ultrafilter. Hence, the first claim is proven.

As for the second statement, it is clear that $x+y\in U$ if either $x\in U$ or $y\in U$ by property $(2)$ of filters. Suppose, on the other hand, that $x,y\notin U$. Then, by the previously proven claim, we would have that $\overline{x},\overline{y}\in U$, and $\overline{x}\cdot\overline{y}\in U$, and therefore $\overline{\overline{x}\cdot\overline{y}}=x+y\notin U$. Thus, $x+y\in U$ $\iff$ $x\in U$ or $y\in U$, as claimed. $\blacksquare$

This leads to the following fact, which shows that every boolean algebra can be represented as a field of sets:

Proposition 2. Let $X$ be the set of ultrafilters on some boolean algebra $\mathfrak{A}$, and define $h(a) = {U\in X: a\in U}$, so that $h(a)$ is the set of ultrafilters containing $a$. Then $h$ is an isomorphism between the boolean algebra in question and the field of sets given by

Proof. The following observations suffice to show that $h$ is an isomorphism:
- $h(x+y)=h(x)\cup h(y)$ follows from the previous proposition, because an ultrafilter $U$ contains $x+y$ iff it contains $x$ or contains $y$
- $h(\overline{x})=\overline{h(x)}$, again following from the previous proposition
- $h(x\cdot y)=h(x)\cap h(y)$, since
- $h(0)=\varnothing$, because the only filter containing $0$ is $A$, which is not proper and therefore not an ultrafilter
- $h(1)=X$, because $h(1)=h(\overline{0})=\overline{h(0)}=\overline{\varnothing}=X$
- $h$ is injective, because if $x,y\in A$ are distinct, then $(x\cdot \overline{y})+(\overline{x}\cdot y) \ne 0$, implying that $(h(x)\cap \overline{h(y)})\cup (\overline{h(x)}\cap h(y))\ne \varnothing$, meaning that $h(x)\ne h(y)$ (the "symmetric difference" of $h(x)$ and $h(y)$ is nonempty)
- $h$ is bijective because it is injective and the set ${h(a):a\in A}$ is the image of its domain
$\blacksquare$

model-theory

set-theory

measure-theory

back to home page