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.
Best Answer
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.