Reference for equivalence of Boolean Prime Ideal Theorem and the Completeness theorem for propositional logic

Question

I've read in Kaye's The Mathematics of Logic that the Boolean Prime Ideal Theorem is equivalent to the Completeness Theorem for propositional logic, however the proof of the completeness theorem given in the book uses Zorn's lemma, which I know is strictly stronger than the BPIT. Can anyone recommend a resource which would provide more information on how to show this equivalence? I'm not sure where you'd start to prove this.

Answer 1

I'd definitely start with Jech's Axiom of Choice book. Chapter 2, Section 3 is about the Boolean Prime Ideal Theorem.

There, the Compactness Theorem is given for first-order logic, but the Consistency Principle, as stated is the Completeness Theorem for propositional logic.

The two can be adapted for a proof of the Compactness Theorem for propositional logic, as well as the Completeness Theorem for first-order logic are both equivalent, as well, to the Boolean Prime Ideal Theorem.

---

In a very deep sense, this is something that appears in the study of large cardinals as well.

We say that $\kappa$ is a strongly compact cardinal if every $\kappa$-complete filter extend to a $\kappa$-complete ultrafilter. This is equivalent to the assertion that every $\cal P_\kappa(\lambda)$-tree has a branch, as well as to the Compactness Theorem for $\cal L_{\kappa,\kappa}$.

Now, a "binary mess" is nothing more than a $\mathcal P_\omega(X)$-tree. So this is just a "tree property" in disguise.

Answer 2

Let $\mathsf{PROP}$ denote the set of propositions.

On $\mathsf{PROP}$ we have an equivalence relation $\sim_{\vDash}$ defined by: $$p\sim_{\vDash}q\iff p\vDash q\text{ and } q\vDash p$$ where $p\vDash q$ stands for: $v\left(p\right)\leq v\left(q\right)$ for every valuation on $\mathsf{PROP}$. (we could also say that $p\sim q$ iff $v\left(p\right)=v\left(q\right)$ for every valuation on $\mathsf{PROP}$ or that $p$ and $q$ are logically equivalent).

For $p\in\mathsf{PROP}$ let $\left[p,\vDash\right]$ the equivalence class wrt this relation and let $\mathsf{P}_{\vDash}:=\left\{ \left[p,\vDash\right]\mid p\in\mathsf{PROP}\right\} $. Then we can make $\mathsf{P}_{\vDash}$ a "semantical" Boolean algebra by defining multiplication, addition and complementation by:

• $\left[p,\vDash\right]\cdot\left[q,\vDash\right]=\left[p\wedge q,\vDash\right]$
• $\left[p,\vDash\right]+\left[q,\vDash\right]=\left[p\vee q,\vDash\right]$
• $\left[p,\vDash\right]'=\left[\neg p,\vDash\right]$

Further every valuation $v$ on $\mathsf{PROP}$ induces a map $\bar{v}:\mathsf{P}_{\vDash}\to\left\{ 0,1\right\} $ prescribed by $\left[p,\vDash\right]\mapsto v\left(p\right)$.

In a similar way we construct a "syntactical" Boolean algebra $\mathsf{P}_{\vdash}$ where the elements are denoted by $\left[p,\vdash\right]$ and are the equivalence classes of the relation $\sim_{\vdash}$ defined by: $$p\sim_{\vdash}q\iff p\vdash q\text{ and }q\vdash p$$

Then soundness (i.e. the fact that $p\vdash q$ implies that $p\vDash q$) implies that the map $\iota:\mathsf{P}_{\vdash}\to\mathsf{P}_{\vDash}$ prescribed by $\left[p,\vdash\right]\mapsto\left[p,\vDash\right]$ is well defined and it is easy to check that this map is a surjective morphism.

Proving completeness is nothing more than proving that actually $\mathsf{P}_{\vdash}$ and $\mathsf{P}_{\vDash}$ are exactly the same and for this it is enough to prove that $\iota$ is also injective.

Now that is the place where BPIT comes in.

Let it be that $\left[p,\vdash\right]$ and $\left[q,\vdash\right]$ are distinct. Then according to BPIT an ultrafilter $U$ exists on $\mathsf{P}_{\vdash}$ such that it contains exactly one of the elements $\left[p,\vdash\right]$ an $\left[q,\vdash\right]$. WLOG let's say that $\left[p,\vdash\right]\in U$ and $\left[q,\vdash\right]\notin U$. The set $\Gamma=\left\{ r\in\mathsf{PROP}\mid\left[r,\vDash\right]\in U\right\} $ is then maximally consistent with $p\in\Gamma$ and $q\notin\Gamma$. But it can be proved that then a valuation $v$ exists such that $v\left(p\right)=1$ and $v\left(q\right)=0$ or equivalently $\bar{v}\left(\left[p,\vDash\right]\right)=1$ and $\bar{v}\left(\left[q,\vDash\right]\right)=0$. (this valuation is induced by giving all propositional letters in $\Gamma$ value $1$ and all others value $0$)

This implies that $\left[p,\vDash\right]$ and $\left[q,\vDash\right]$ are also distinct. Proved is now that $\iota$ is indeed injective, hence moreover is the identity and that the Boolean algebras $\mathsf{P}_{\vdash}$ and $\mathsf{P}_{\vDash}$ are the same.