# Proving Craig's Interpolation Theorem on Propositional Logic using Hintikka Sets and Craig Pairs

I'm working through Mathematical Logic by Ian Chiswell and Wilfrid Hodges. And I'm stuck at exercise 3.10.2 d.

It asks to deduce Craig's Interpolation Theorem for propositional logic with an (at most) countably infinite signature. Here is exercise 3.10.2:

Let σ and τ be signatures. Suppose $$Φ$$ is a set of formulas of $$LP(σ)$$ and $$Ψ$$ is a set of formulas of $$LP(τ)$$. We say that $$(Φ, Ψ)$$ is a Craig pair if there is no formula $$θ$$ of $$LP(σ ∩ τ)$$ such that $$Φ \vdash_σ θ$$ and $$Ψ \vdash_τ ¬θ$$.

(a)  Show that if $$(Φ, Ψ)$$ is a Craig pair then both $$Φ$$ and $$Ψ$$ are syntactically consistent.

(b)  Show that if $$(Φ, Ψ)$$ is a Craig pair and both $$Φ$$ and $$Ψ$$ are Hintikka sets of formulas of $$LP(σ)$$ and $$LP(τ)$$, respectively, then $$Φ ∪ Ψ$$ is a Hintikka set.

(c)  Show that if $$(Φ, Ψ)$$ is a Craig pair, then there are Hintikka sets $$Φ'$$ of formulas of $$LP(σ)$$, and $$Ψ'$$ of formulas of $$LP(τ)$$, such that $$Φ ⊆ Φ'$$ and $$Ψ ⊆ Ψ'$$ and $$(Φ', Ψ')$$ is a Craig pair. [The proof is very similar to that of Lemma 3.10.6. List all the formulas of $$LP(σ ∪ τ)$$.]

(d)  Deduce from (a)–(c) that if $$φ$$ is a formula of $$LP(σ)$$, $$ψ$$ is a formula of $$LP(τ)$$ and $$\{φ\} \models_{σ∪τ} ψ$$, then there is a formula $$θ$$ of $$LP(σ ∩ τ)$$, such that $$\{φ\} \vdash_σ θ$$ and $$\{θ\} \vdash_τ ψ$$. (This result is known as Craig’s Interpolation Theorem; the formula $$θ$$ is the interpolant. Craig’s Interpolation Theorem can be extended to first-order logic, by a very similar proof to that in this exercise.)

I'm interested in the intended solution especially because of the note after the question that says the theorem "...can be extended to first-order logic, by a very similar proof...".

Some information that may be relevant and/or book-specific:

• $$LP(σ)$$ is used to denote the "language of propositions" with $$σ$$ as its signature.

• The book presumes very little set theory knowledge. I think that's why the question doesn't explicitly say it expects the answer for countable signatures. Lemma 3.10.6 mentioned in (c) also only talks about languages with countable signatures. The lemma uses Gödel numbers to list all formulas of a language.

• The book teaches classical logic and uses Gentzen-style natural deduction. $$Φ \vdash_σ θ$$ means "There's a $$σ$$-derivation of $$θ$$ with the assumption set $$Φ$$" where a σ-derivation is a derivation of $$LP(σ)$$. While $$Φ \models_σ θ$$ means "each $$σ$$-structure that satisfies all formulas of $$Φ$$, satisfies $$θ$$ too."

• Completeness of the proof-system defined in the book is proved prior to these exercises. (only for languages with countable signature)

• In the book, Hintikka sets are defined as the following for a propositional language with only ∧, ¬ and ⊥ as its logical symbols.

We say that a set Γ of formulas of (the stripped-down) LP is a Hintikka set (for LP) if it has the following properties:

(1) If a formula $$(φ ∧ ψ)$$ is in $$Γ$$ then $$φ$$ is in $$Γ$$ and $$ψ$$ is in $$Γ$$.

(2) If a formula $$(¬(φ ∧ ψ))$$ is in $$Γ$$ then at least one of $$(¬φ)$$ and $$(¬ψ)$$ is in Γ.

(3) If a formula $$(¬(¬φ))$$ is in $$Γ$$ then $$φ$$ is in $$Γ$$.

(4) $$⊥$$ is not in $$Γ$$.

(5) There is no propositional symbol $$p$$ such that both $$p$$ and $$(¬p)$$ are in $$Γ$$.

This is how I think about Hintikka sets: I learned tree proofs from this video. I noticed that if you write each formula of a syntactically consistent set of formulas on top of each other, then try to proceed to do a tree proof, you will get branches that won't "close". And those branches consist of Hintikka sets. Here is an image of an example

Remember that I'm only asking (d) but had to include others in the excerpt. I'm concerned that the excerpt is too long.

By the way, I'm in my second semester of learning math; just in case that's relevant.

I did try to plan a way of proving it with use of the Principle of Irrelevance, and disjunctive normal forms (which are mentioned prior in the book) but it doesn't use (a)-(c). And if I remember right, it turned out pretty long too.

If you see the proof that is being hinted at, I'd really appreciate it if you explain. Thank you for reading.

• Could you please clarify the notion of Hintikka sets? Is this the same notion as that of maximal consistent sets? Commented Apr 27, 2021 at 15:31
• @sequitur I'm sorry for replying really late. No, they aren't the same notions but all maximally consistent sets, in this case, are also Hintikka sets (I may be wrong here). I edited to add a description of Hintikka sets.
– t42
Commented Apr 30, 2021 at 16:49
• You're quite right: All maximal consistent sets are Hintikka sets. Commented May 1, 2021 at 21:56

We have $$\{\phi\} \models_{\sigma\cup\tau} \psi$$

So all model of $$\{\phi\}$$ is also a model of $$\psi$$

So $$\{\phi,\neg\psi\}$$ doesn't have a model

So $$\{\phi,\neg\psi\}$$ isn't a Hintikka set (by Lemma 3.10.5)

So, by item (b), either $$(\{\phi\},\{\neg\psi\})$$ is not a Craig pair or the sets $$\{\phi\}$$ and $$\{\neg\psi\}$$ are not both Hintikka sets. (OBS: $$\{\phi,\neg\psi\} = \{\phi\} \cup \{\neg\psi\}$$)

If $$(\{\phi\},\{\neg\psi\})$$ is a Craig pair, by item (c), there are Hintikka sets $$\Phi'$$ and $$\Psi'$$ such that $$\{\phi\} \subseteq \Phi'$$ and $$\{\neg\psi\} \subseteq \Psi'$$ and $$(\Phi',\Psi')$$ is a Craig pair

So, if $$(\Phi',\Psi')$$ is a Craig pair, $$\Phi' \cup \Psi'$$ is a Hintikka set (by item (b) again)

But this is impossible, because $$\Phi' \cup \Psi'$$ doesn't have a model

So ({ϕ},{¬ψ}) is not a Craig pair

So there is a formula $$\theta \in LP(\sigma \cap \tau)$$ such that: $$\{\phi\} \vdash \theta$$ and $$\{\neg\psi\} \vdash \neg\theta$$

If the second sequent is correct, so is $$\{\theta\} \vdash \psi$$

So $$\theta$$ is the interpolant

P.S.: I fixed my first solution because it had a small error as stated by @t42 in the comments.

• Hi! I don't understand the step on the 7th part. In this step did you infer that $Φ'$ and $Ψ'$ cannot simultaneously be Hintikka sets only from the assertion that $\{φ\}$ and $\{ψ\}$ cannot simultaneously be Hintikka sets? Because I think I found a counterexample: Let $A$ be a sentence, $φ$ be $A$ and $ψ$ be $A∧A$. Then $\{ϕ\}$ is a Hintikka set and $\{¬ψ\}$ isn't. Now let $Φ′$ be $\{ϕ\}$ and $Ψ′$ be $\{¬ψ, ¬A\}$. These are both Hintikka... Anyway I managed to find a proof that I think is valid by modifying yours. I'll submit it shortly. Thank you for your reply! :)
– t42
Commented Feb 13, 2022 at 16:22
• Hello. You're right. I will fix my solution. Thanks. Commented Feb 14, 2022 at 11:36

I came to this proof by modifying the answer submitted by @lcmpereira.

• We have $$\{φ\} \models_{σ∪τ} ψ$$.

• So each model of $$φ$$ is also a model of $$ψ$$.

• Then $$\{φ, ¬ψ\}$$ doesn't have any models, neither do its supersets. (*)

• Now assume, for contradiction, that $$(\{φ\}, \{¬ψ\})$$ is a Craig pair.

• Then, by item (c), there are Hintikka sets $$Φ′$$ and $$Ψ′$$ such that $${ϕ}⊆Φ′$$ and $${¬ψ}⊆Ψ′$$ and $$(Φ′,Ψ′)$$ is a Craig pair.

• Then ,by item (b), $$Φ'∪Ψ'$$ is a Hintikka set. (**)

• But $$Φ'∪Ψ'$$ is a superset of $$\{φ, ¬ψ\}$$ so ,by (*), it doesn't have any models.

• Then $$Φ'∪Ψ'$$ isn't a Hintikka set (by Lemma 3.10.5 in the book). This contradicts with (**), so:

• $$(\{φ\}, \{¬ψ\})$$ isn't a Craig pair.

• This means there must be a formula $$θ∈LP(σ∪τ)$$ such that $${ϕ}⊢_σθ$$ and $${¬ψ}⊢_τ¬θ$$.

• From $${¬ψ}⊢_τ¬θ$$, we can deduce $${θ}⊢_τψ$$... (For example using sequent calculus...)

• Then we have both $${ϕ}⊢_σθ$$ and $${θ}⊢_τψ$$ so the proof is complete with $$θ$$ as the interpolant. QED!

In hindsight I think in order to find this proof, one needs to first come up with these last three steps. Then the rest follows.

Something that bothers me about this proof is that it doesn't use item (a) so it may not be the intended proof but I'm satisfied with this.

• Small typo in definition of $\theta$. The definition of $\theta$ is that it is from $LP(\sigma \cap \tau)$. Commented Jun 9, 2023 at 18:49
• You can use item (a) directly. Since {φ, ¬ψ} don't have a model, they aren't consistent. Thus they aren't a Craig pair. Commented Jun 9, 2023 at 18:50