# Constructing an example that supports the Propositional Interpolation Theorem

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?

• 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. – Carl Mummert Sep 7 '10 at 1:09
• You're quite right, silly of me to do that. Thanks. – yunone Sep 7 '10 at 1:14
• 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. – Carl Mummert Sep 7 '10 at 1:17
• 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$? – yunone Sep 7 '10 at 1:23