 Proof: The proof proceeds by induction on the number of steps in the proof of \(\phi\). Crucial to this proof is the fact that \(\theta=\theta(t|t')\) whenever \(\theta\) does not contain \(t\) or \(t'\). When the number of steps in the proof of \(\phi\) is one, this means that the last (and only) rule applied is (As) or (=I). Then, since \(\phi\) does not contain \(t\) or \(t'\), if \(\Gamma_1\vdash\phi\) we simply apply the same rule ((As) or (=I)) to \(\Gamma_2\) to get \(\Gamma_2\vdash\phi\). Assume that there are \(n&gt;1\) steps in the proof of \(\phi\), and that Lemma 7 holds for any proof with less than \(n\) steps. Suppose that the \(n^{th}\) rule applied to \(\Gamma_1\) was (\(\amp I\)). Then \(\phi\) is \(\psi\amp\chi\), and \(\Gamma_1\vdash\phi\amp\chi\). But then we know that previous steps in the proof include \(\Gamma_1\vdash\psi\) and \(\Gamma_1\vdash\chi\), and by induction, we have \(\Gamma_2\vdash\psi\) and \(\Gamma_2\vdash\chi\), since neither \(\psi\) nor \(\chi\) contain \(t\) or \(t'\). So, we simply apply (\(\amp I\)) to \(\Gamma_2\) to get \(\Gamma_2\vdash\psi\amp\chi\) as required. Suppose now that the last step applied in the proof of \(\Gamma_1\vdash\phi\) was (\(\amp E\)). Then, at a previous step in the proof of \(\phi\), we know \(\Gamma_1\vdash\phi\amp\psi\) for some sentence \(\psi\). If \(\psi\) does not contain \(t\), then we simply apply (\(\amp E\)) to \(\Gamma_2\) to obtain the desired result. The only complication is if \(\psi\) contains \(t\). Then we would have that \(\Gamma_2\vdash (\phi\amp\psi)(t|t')\). But, since \((\phi\amp\psi)(t|t')\) is \(\phi(t|t')\amp\psi(t|t')\), and \(\phi(t|t')\) is just \(\phi\), we can just apply (\(\amp E\)) to get \(\Gamma_2\vdash\phi\) as required. The cases for the other rules are similar.