What is the relationship between ultrafilters and propositional theories?

Question

I am learning more about how to use ultrafilters by using them to prove several of the typical results which appear as applications of propositional (or first-order) compactness.

Generally speaking, as I try to work out the proofs, I begin to see that ultrafilters produce precise descriptions/specifications of certain desirable objects (in the sense of what we want to prove) in a way that the ultrafilter lists the (set-theoretic) properties that we want our hypothetical object to have. This is similar to what we do when we define the propositional atoms and the set of sentences encoding what we want to prove, and then proceed to showing satisfiability.

For example, consider the graph coloring theorem of De Bruijn–Erdős.

A graph $\Gamma$ is $k$-colorable if and only if every finite subgraph of $\Gamma$ is $k$-colorable.

Where $\Gamma=(G,\mathcal{A})$ (G is the set of vertices and $\mathcal{A}$ the binary relation definiting the edges), $k$ is a positive integer and a $k$-coloring of $\Gamma$ is a function $f:G\rightarrow \{c_{1},\ldots,c_{k}\}$ such that $f(u)\neq f(v)$ whenever $(u,v)\in \mathcal{A}$ (adjacent vertices have different colors).

Consider the $\Leftarrow$ implication, i.e. assume that every finite subgraph of $\Gamma$ is $k$-colorable.

Via propositional compactness: We define a language $L$ to consist of propositional atoms $p_{vi}$, for each vertex $v$ and each $1\leq i\leq k$. Intuitively, $p_{vi}$ expresses vertex $v$ gets color $c_{i}$ when true. Then we define $S$ to be the set of $L$-formulas:

1. $(p_{v1}\vee\ldots\vee p_{vk})$ for all vertices $v\in G$.
2. $\neg(p_{vi}\wedge p_{vj})$ for all $v\in G$ and $1 \leq i<j\leq k$.
3. $\neg(p_{ui}\wedge p_{vi})$ for all $(u,v)\in \mathcal{A}$ and $1\leq i\leq k$.

And away we go proving finite satisfiability so that compactness will give us a truth valuation $v$ satisfying $S$, which we then use to define $k$-coloring $f$ of $\Gamma$ by $$f(v) = c_{i}\text{ iff }v(p_{vi})=\top.$$

Via ultrafilters: We consider the set $C$ of all functions $f:G\to\{c_{1},\ldots,c_{n}\}$, and for each finite set of vertices $H\subseteq G$ we let $$A_{H}=\{f\in F:f_{H}\text{ is a $k$-coloring of $\Gamma_{H}$}\},$$ where $\Gamma_{H}=(H,\mathcal{A}|_{H})$ denotes the finite subgraph of $\Gamma$ obtained by restricting $\mathcal{A}$ to $H$. Then we let $$F=\{X\in\mathcal{P}(C):A_{H}\subseteq X\text{ for some finite $H\subseteq G$}\}$$

Then $F$ is a filter on $\mathcal{P}(C)$ and it can be extended to an ultrafilter $U$ via the ultrafilter theorem. If for each vertex $v\in G$ and $1\leq i\leq k$ we let $$P_{vi}=\{f\in C:f(v)=c_{i}\}$$ the ultrafilter allows us to show that

1. For any $v\in G$ there is some $1\leq i\leq k$ such that $P_{vi}\neq\emptyset$.
2. For any $v\in G$ and $1\leq i<j\leq k$ we have $P_{vi}\cap P_{vj}=\emptyset$.
3. For each $v\in G$ and $1\leq i<j\leq n$ $P_{vi}\sqcup \bar{P}_{vi}=C$, where $\sqcup$ denotes disjoint union and $\bar{P}_{vi}=\{f\in S:f(v)\neq c_{i}\}$. Hence, for each $v\in G$ and $1\leq i\leq k$ either $P_{vi}\in U$ or $\bar{P}_{vi}\in U$.

Therefore, the ultrafilter gives us the $k$-coloring, since 1-3 above show that for each $v\in G$ there is a unique $i_{v}$ such that $P_{vi_{v}}\in U$, effectively defininig a $k$-coloring of $\Gamma$ by $$f(v) = c_{i}\text{ iff } P_{vi}\in U$$ in which case $f(v)=i_{v}$.

The suggestive relationship between the propositional atoms $p_{vi}$ and the sets $P_{vi}$ is clear. Moreover, so is the relationship between 1-3 defininig the propositional theory $S$ and 1-3 of the ultrafilter approach. Hence, in a rough, imprecise sense, I can see that the ultrafilter $U$ "is" the theory $S$. The ultrafilter is like a truth-tester of what we want, playing the role of $v$. That is $$P_{vi}\in U\text{ iff }v(p_{vi})=\top.$$

That is, the desired $k$-coloring of $\Gamma$ will be given by $v$ (satisfying $S$) or equivalently by $U$.

Questions: What is the precise relationship between propositional or first-order (satisfiable) theories and ultrafilters? Since logical compactness and the ultrafilter theorem are $\mathsf{ZF}$-equivalent, is there a standard way of "translating" a proof via logical compactness into a proof via ultrafilters, and vice versa?

I would be very appreciative if standard references are provided, as I am learning all of this on my own, with only online access.

Answer 1

The relationship is Boolean algebras

• A filter in a boolean algebra corresponds $1:1$ with surjective homomorphisms from that algebra to a some other algebra.
• An ultrafilter in a boolean algebra corresponds $1:1$ with surjective homomorphisms of that algebra to the 2-point algebra $\{0,1\}$ (or $\{F,T\}$ if you prefer.)

Let $A, B$ be boolean algebras with $\phi:A\to B$ a surjective homomorphism. The corresponding filter is $F_\phi=\{a\in A: \phi(a) = 1_B$}. If $B\simeq\{0, 1\}$ then $F_\phi$ is an ultrafilter.

Conversely, let $F$ be a filter in $A$. You can construct a quotient algebra $B=A/F$ from this. The equivalence relation on $A$ to construct the quotient is $$a_1 \equiv_F a_2 \iff ((a_1 \land a_2)\lor (\neg a_1 \land \neg a_2))\in F$$ In particular $a\equiv_F 1_A \iff (a\land 1_A)\in F\iff a\in F$. The quotient map $\phi_F: A\to A/F$ is simply the map sending each element to its equivalence class. If $F$ is an ultrafilter then $A/F\simeq \{0,1\}$.

Now let $S$ be a set of propositional atoms. Let $A(S)$ be the free boolean algebra on $S$. To say that some theory $T\subseteq A(S)$ has a model is equivalent to saying there is a homomorphism $\psi:A(S)\to\{0,1\}$ such that $\psi(t)=1$ for all $t \in T$. This is equivalent to saying there is an ultrafilter containing $T$. By the ultrafilter lemma, this is equivalent to saying there is some filter containing $T$. This in turn is equivalent to saying that $T$ is a filter sub-base. A filter sub-base is a collection that satisfies the 'finite meet property' - i.e. if $u_1,\dots,u_n\in T$ then $u_1\land\dots\land u_n \ne 0$. Since it is apparent that $T$ has the 'finite meet property' iff every finite subset of $T$ has the 'finite meet property' - the compactness theorem is equivalent to the ultrafilter lemma.

For completion of terminology - A filter base is a subset that is closed under finite meets and does not contain zero. If $T$ is a filter subbase then the collection of all finite meets of members of $T$ is a filter base. If $T$ is a filter base then the set $\{x: \exists t\in T\; t\lor x = x$} is a filter. It is the smallest filter containing the filter base (or subbase) you start from. Notice that $t\lor x=x \iff t\le x$ is the order relation in a Boolean algebra.

Edit: the argument in the 2nd to last paragraph shows that ultrafilter lemma $\implies$ compactness theorem. The opposite direction needs more work. If $F$ is a filter, it satisfies the 'finite meet property'. It is enough to show that any $\psi = \phi_1\land\dots\land\phi_n \ne 0$ has a model. This is a theorem of boolean algebra on finitely many atomic propositions that a formula that is not a contradiction has a satisfying assignment. It is proved by induction on the number of atomic propositions (or length of the formula) by showing a formula can be converted to disjunctive normal form. In DNF - if the formula is not zero, the satisying assignments can be read directly from the conjunctions that join to make it up. Finally, any finite subset of $F$ has a model so by compactness $F$ has a model which is equivalent to saying $F$ is contained in an ultrafilter.

Answer 2

Ultraproducts provide a relationship as well. Note how the first couple of points of John Doe's answer make the connection with Boolean algebras clear, but ultraproducts are worth examining on their own. The book by Bell & Slomson, Models and Ultraproducts: An Introduction, mentioned in a comment proved useful. In chapter 5, ultraproducts are discussed in the context of first-order logic and it was good practice to try to reduce the construction to propositional logic.

In the example I used (the coloring theorem) we have a propositional theory $S$ which is finitely satisfiable because every finite subgraph of $\Gamma$ is $k$-colorable. That is, if $n\subseteq S$ is finite, the subgraph formed by the vertices mentioned in the sentences of $n$ is $k$-colorable via a $k$-coloring $f_{n}$. Therefore, we can define a truth valuation satisfying $n$ by $$v_{n}(p_{vi}) = \top\text{ iff }f_{n}(v)=c_{i}.$$ Therefore, we have a family $\{v_{n}:n\text{ is a finite subset of $S$}\}$ of truth valuations, where $v_{n}$ satisfies the finite subset $n\subseteq S$. How do we get a single truth valuation $v$ for $S$ from all these $v_{n}$? Well, the idea suggested by the example is that for an $L$-formula $\varphi\in S$ the value of $v(\varphi)$ in $\{\top,\bot\}$ is the one which occurs most frequently among all the values $v_{n}(\varphi)$. Now, in our example, saying that $v_{n}(p_{vi})=\top$ is the same as saying that the set $P_{vi}\in U$. Therefore, the ultrafilter is the arbitrer telling us which value of $v_{n}(p_{vi})$ occurs most frequently. Of course, we will ensure this will be true for general $L$-formulas, not just atoms.

More formally, let $$N_{S}=\{n\in\mathcal{P}(S): n\text{ is finite}\},$$ and for each $\varphi\in S$ let $$X_{\varphi}=\{n\in N_{S}:v_{n}(\varphi)=\top\}$$ Note that if $\varphi = p_{vi}$, then $X_{\varphi}\cong P_{vi}$ via $n\to f_{n}$.

Then, generalizing our example, we would like to be able to define the truth assignment $v$ on $S$ form the $v_{n}$ by saying that $v(\varphi)=\top$ if and only if $X_{\varphi}$ is in an appropriate ultrafilter. We do this as follows:

For each $\varphi\in S$ let $Y_{\varphi}=\{n\in N_{S}:\varphi\in n\}$, and define $$\mathcal{Y}_{S}=\{Y_{\varphi}:\varphi\in S\}.$$

Since $\mathcal{Y}_{S}$ has the finite intersection property, the set $$\mathcal{F}=\{H\in\mathcal{P}(N_{s}):\bigcap_{Y\in F}Y\subseteq H\text{ for some finite $F\subseteq\mathcal{Y}_{S}$}\}$$ is a filter which, and by the ultrafilter theorem, can be extended to an ultrafilter $U'$ on $N_{S}$.

Then defining $v$ as described above is simply $$v(\varphi) = \begin{cases} \top & \text{if } X_{\varphi}\in U'\\ \bot & \text{otherwise} \end{cases}$$ That is, $v$ is the propositional version of the ultraproduct of the family $\{v_{n}:n\in N_{S}\}$.

This is well defined from the properties of the ultrafilter. Note that $\mathcal{Y}_{S}\subseteq U'$, and for each $\varphi\in S$ we have $Y_{\varphi}\in U$ and $Y_{\varphi}\subseteq X_{\varphi}$ imply $X_{\varphi}\in U'$ (so that $X_{\neg\varphi}=N_{S}-X_{\varphi}\not\in U'$)

The "translation" or correspondence between the ultrafilter $U$ of the example and the ultrafilter $U'$ is an offshoot of the correpondence between the $X_{p_{vi}}$ and the $P_{vi}$.

Summarizing: If we have a propositional theory $S$ which is finitely satisfiable, we can use the family of truth valuations satisfying the finite subsets of $S$ to define an ultrafilter $U'$ encoding the theory (i.e. the propositional theory $S$ "is" the ultrafilter $U'$) which yields an ultraproduct truth valuation $v$ satisfying $S$ (note how this essentially proves the compactness theorem for propositional logic) The process is reversible.