Past exam of the logic and set theory course of the University of Oxford / 2008 / A / 1 / f

Fix the particular occurrence of $\alpha$ that is being replaced. The subformula analysis above makes it a node of the formula syntax tree of $\varphi$. Proceed by structural induction on the surrounding logical formula.

If this node is the root, the subformula replacement gives $\beta$, already a logical formula. Otherwise, if $\varphi =\neg \psi$, the chosen occurrence lies inside $\psi$. The induction hypothesis gives a logical formula ${\psi }^{\prime }$ after the subformula replacement there, and the whole result is the logical formula $\neg {\psi }^{\prime }$. If $\varphi =(\psi \to \chi )$, a proper chosen occurrence lies in exactly one of the two children. Replacing inside that child gives either $({\psi }^{\prime }\to \chi )$ or $(\psi \to {\chi }^{\prime })$, each a logical formula by the formation rule. A logical variable has no proper subformula, so there is no additional base case.

Therefore replacing the designated subformula occurrence by any logical formula preserves well-formedness. The argument concerns one chosen occurrence; it does not require simultaneous subformula replacement of every occurrence of the same string.