$\newcommand{\atoms}[1]{\mathscr{A}\left(#1\right)}$ $\newcommand{\abs}[1]{\lvert#1\rvert}$
We define $\atoms{F}$ to be the set of all atoms in a formula $F$.
The Craig interpolation lemma is stated as follows: Let $A$ and $B$ be formulae and let $S = \atoms{A} \cap \atoms{B}$. Assume that $S \neq \emptyset$. If $\vDash \left(A \rightarrow B\right)$, then there is some formula $C$ such that $C$ is composed only of elements from $S$, $\vDash \left(A \rightarrow C\right)$ and $\vDash \left(C \rightarrow B\right)$.
I am having trouble making one assumption that leads to the completion of my proof. My proof goes as follows.
We conduct mathematical induction on $\abs{\atoms{A} \setminus \atoms{B}}$ ($\abs{\cdot}$ denotes cardinal of a set).
First assume $\abs{\atoms{A} \setminus \atoms{B}} = 0$. Then all atoms of $A$ are in $B$. We have $S = \atoms{A}$. It is clear that $A \rightarrow A$ and $A \rightarrow B$. Thus, there is some formula $C$ such that $C$ is composed of atoms only from $S$ such that $\left(A \rightarrow C\right)$ and $\left(C \rightarrow B\right)$ are valid.
Next, assume $n \in \mathbb{N}$ and for any formulae $A$ and $B$, if $\abs{\atoms{A} \setminus \atoms{B}} \leq n$, then the statement in the lemma holds (induction hypothesis). Now consider $\abs{\atoms{A} \setminus \atoms{B}} = n + 1$. As $n + 1 > 0$, it is clear that \begin{equation*} \atoms{A} \setminus \atoms{B} \neq \emptyset. \end{equation*} Then there is some atom $P$ such that $P \in \atoms{A}$ and $P \not\in \atoms{B}$. Also, as \begin{equation*} \atoms{A} \cap \atoms{B} \neq \emptyset, \end{equation*} there is some atom $Q$ such that $Q \in \atoms{A} \cap \atoms{B}$. Let \begin{equation*} A^{\prime} \equiv \left(A\left(Q / P\right) \vee A\left(\neg Q / P\right)\right). \end{equation*} It is my desire to argue that as $\vDash \left(A \rightarrow B\right)$, $\vDash \left(A^{\prime} \rightarrow B\right)$, so that I can use induction hypothesis, as $\abs{\atoms{A^{\prime}} \setminus \atoms{B}} = n$. Intuitively this seems to be the case. But how to prove it?
I seem to be able to prove this using structural induction.