I'm working on an exercise for William Craig's Interpolation Theorem for propositional logic, and I'm having troubles proving the following lemma:
Let ϕ and ψ be sentences of propositional logic and suppose that ϕ |= ψ, that ϕ is not a contradiction and that ψ is not a tautology. Then, Atom(ϕ) and Atom(ψ) are not disjoint.
Can anyone help me with a strategy and proof for this one? Many thanks!
Do a proof by contradiction. Assume that $Atom(\phi)\cap Atom(\psi)=\emptyset$ and prove that we get a contradiction.
Let $v_1$ be a valuation such that $v_1(\phi)=T$ (this is possible since $\phi$ is not a contradiction) and $v_2$ be a valuation such that $v_2(\psi)=F$ (this is possible since $\psi$ is not a tautology). Since the atoms of $\psi$ and $\phi$ are disjoint we may create a valuation $v$ such that $v(p)=v_1(p)$ for $p\in Atom(\phi)$ and $v(q)=v_2(q)$ for $q\in Atom(\psi)$. Now it follows that $v(\phi)=T$ and $v(\psi)=F$, thus $\phi\not\models \psi$ which is a contradiction.