Franklin's Notes


Interpolation Theorem

In sentential logic , the Interpolation Theorem states the following:

Interpolation Theorem. If $\varphi \vDash \psi$, then either
1. $\varphi$ is refutable;
2. $\psi$ is valid; or
3. there exists a sentence $\theta$ such that $\varphi\vDash\theta$, $\theta\vDash\psi$, and every sentence symbol which occurs in $\theta$ also occurs in both $\varphi$ and $\psi$

Proof. Let $V_\varphi$ be the set of sentence symbols occurring in $\varphi$ but not in $\psi$, $V_\psi$ be the set of sentence symbols occurring in $\psi$ but not $\varphi$, and $V$ be the set of sentence symbols occurring in both $\varphi$ and $\psi$. If $V$ is empty, then clearly case $(3)$ cannot hold. In this situation, if there is an assignment for which $\varphi$ is true and an assignment for which $\psi$ is false, then there is an assignment for which $\varphi$ is true and $\psi$ is false (since they depend on disjoint sets of sentence symbols), contradicting $\varphi\vdash\psi$. Thus, we must have that either $\varphi$ is never true, which is case $(1)$, or $\psi$ is never false, which is case $(2)$.

Now suppose that $V$ is nonempty. Since $V$ is finite, we are able to build a statement $\theta$ that has prescribed truth values for each possible assignment of the sentence symbols in $V$. If $f:V\to {\mathrm{T},\mathrm{F}}$ is an assignment of the sentence symbols in $V$, then define the truth value of $\theta$ casewise as follows:

  1. If there exists any extention of the assignment $f$ to $V\cup V_\psi$ for which $\psi$ fails, then let $\theta$ have truth value $\mathrm{F}$ for the assignment $f$.
  2. If there exists any extension of the assignment $f$ to $V\cup V_\varphi$ for which $\varphi$ holds, then let $\theta$ have truth value $\mathrm{T}$ for the assignment $f$.
  3. If $\psi$ holds and $\varphi$ fails for every extension of $f$, let $\theta$ have truth value $\mathrm{T}$ (or $\mathrm{F}$ - in this case, it doesn't matter).

Notice that cases $(1)$ and $(2)$ never "collide" with each other - for if there existed extensions of $f$ to $V\cup V_\psi$ and $V\cup V_\varphi$ for which $\psi$ failed and $\varphi$ held, then there would have to exist an assignment of $V\cup V_\psi\cup V_\varphi$ for which $\psi$ failed and $\varphi$ held, but this would contradict $\varphi\vdash \psi$.

Now, by this definition of $\theta$, we have that $\varphi\vdash\theta$ because $\theta$ has truth value $\mathrm{T}$ whenever any possible assignment of $V\cup V_\varphi$ has truth value $\mathrm{T}$, meaning that $\theta$ holds whenever $\varphi$ does. Similarly, we have $\theta\vdash\varphi$ since $\theta$ has truth value $\mathrm{F}$ whenever any possible assignment of $V\cup V_\psi$ has truth value $\mathrm{F}$, meaning that $\theta$ can only hold when $\psi$ holds. Thus, we have $\varphi\vdash\theta\vdash\psi$ as claimed. $\blacksquare$

To take this further, I think we can even count the number of (nonequivalent) sentences $\theta$ satisfying the above stipulations. Notice that case $3$ in the casewise definition of $\theta$ is where we have some freedom to arbitrarily choose values. For each assignment $f$ of the sentence symbols of $V$ such that $\varphi$ holds and $\psi$ fails for every extension of $f$, we have $2$ choices, true or false, for the truth value of $\theta$. Hence, if $n$ is the number of such assignments $f$, then $2^n$ should be the number of possible nonequivalent statements $\theta$ satisfying $\varphi\vdash\theta\vdash\psi$.

model-theory

sentential-logic

back to home page