 Proof: Again, we proceed by induction on the number of rules that were used to arrive at \(\Gamma_1 \vdash \phi\). Suppose that \(n\gt 0\) is a natural number, and that the theorem holds for any argument that was derived using fewer than \(n\) rules. Suppose that \(\Gamma_1 \vdash \phi\) using exactly \(n\) rules. If \(n=1\), then the rule is either (As) or \((=\)I). In these cases, \(\Gamma_2 \vdash \phi\) by the same rule. If the last rule applied was (&amp;I), then \(\phi\) has the form \((\theta \amp \psi)\), and we have \(\Gamma_3 \vdash \theta\) and \(\Gamma_4 \vdash \psi\), with \(\Gamma_1 = \Gamma_3, \Gamma_4\). We apply the induction hypothesis to the deductions of \(\theta\) and \(\psi\), to get \(\Gamma_2 \vdash \theta\) and \(\Gamma_2 \vdash \psi\). and then apply (&amp;I) to the result to get \(\Gamma_2 \vdash \phi\). Most of the other cases are exactly like this. Slight complications arise only in the rules \((\forall\)I) and \((\exists\)E), because there we have to pay attention to the conditions for the rules.