I'm trying to construct a simple proof of the Propositional Interpolation Theorem. For the following, let $At(\phi)$ be the set of sentence symbols that occur in a sentence $\phi$. Suppose that $\psi$ is a tautological consequence of $\phi$, but neither $\neg\phi$ nor $\psi$ is a tautology, and so $\psi$ is not a tautological consequence of $\phi$ for trivial reasons. I want to show that there is some sentence $\gamma$ such that

i) $\gamma$ is a tautological consequence of $\phi$.

ii) $\psi$ is a tautological consequence of $\gamma$

iii) $At(\gamma)\subseteq At(\phi)\cap At(\psi)$

From iii) $\gamma$ must be constructed from the sentence symbols found both in $\phi$ and $\psi$, so I first showed that $At(\phi)\cap At(\psi)\neq\emptyset$. Since neither $\neg\phi$ nor $\psi$ is a tautology, there must exist truth assignments $V,W$ such that $V(\neg\phi)=F$ and $W(\psi)=F$ and from this $V(\phi)=T$ and $W(\phi)=F$. If $At(\phi)\cap At(\psi)=\emptyset$ we may define a truth assignment for sentence symbols $p_i$,

$U(p_i)=V(p_i)$ if $p_i\in At(\phi)$, $U(p_i)=W(p_i)$ if $p_i\in At(\psi)$.

But then $U(\phi)=V(\phi)=T$, but $U(\psi)=W(\psi)=F$, which contradicts the fact that $\psi$ is a tautological consequence of $\phi$.

My question now is, is there some sort of method to construct $\gamma$ such that conditions i) and ii) are satisfied?

  • 2
    $\begingroup$ Just a note: $\phi$ and $\varphi$ are different ways of writing the same letter, "phi". It's confusing to use them to mean different things in the same sentence. $\endgroup$ – Carl Mummert Sep 7 '10 at 1:09
  • $\begingroup$ You're quite right, silly of me to do that. Thanks. $\endgroup$ – yunone Sep 7 '10 at 1:14
  • $\begingroup$ Responding to the question: There is some way to make $\gamma$, since the interpolation theorem is a theorem. There is a proof of the interpolation theorem for propositional logic at en.wikipedia.org/wiki/Craig_interpolation . If that is not what you are looking for, you may be able to use it as a starting point to make your question more specific. $\endgroup$ – Carl Mummert Sep 7 '10 at 1:17
  • $\begingroup$ Thanks, that should suffice. I guess my original question would be better stated as, is there a way to prove the existence of $\gamma$ without resorting to induction on the number of sentence symbols in $\phi$ that aren't in $\psi$? $\endgroup$ – yunone Sep 7 '10 at 1:23

Induction on the number of sentence symbols is the kind of proof Craig gave originally, and is what logicians call a syntactic proof. It's also possible to give a semantic or model-theoretic proof. Bell and Slomson give one for first-order logic in Chapter 7, section 4 of their text Models and Ultraproducts. I haven't seen a model-theoretic proof for propositional logic. (Submitted as an answer because I don't have enough rep yet to comment.)

| cite | improve this answer | |
  • $\begingroup$ Thanks for mentioning that. I read through the wikipedia article posted above to follow the inductive proof. I was curious to see if there was some alternative proof, so I'll check out the text you linked. $\endgroup$ – yunone Sep 12 '10 at 0:32

You can find some other proofs of the Craig interpolation theorem in this paper by Krajíček.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.