5
$\begingroup$

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
    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.2010-09-07
  • 0
    You're quite right, silly of me to do that. Thanks.2010-09-07
  • 0
    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 http://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.2010-09-07
  • 0
    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$?2010-09-07

2 Answers 2

8

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.)

  • 0
    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.2010-09-12
4

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