 Proof: Here we also proceed by induction on the number of instances of (2)–(7) used to construct the formula. Clearly, the Lemma holds for atomic formulas, since they have no parentheses. Suppose, then, that the Lemma holds for formulas constructed with \(n\) or fewer instances of (2)–(7), and let \(\theta\) be constructed with \(n+1\) instances. If the last clause applied was (3)–(5), then the Lemma holds since \(\theta\) itself begins with a left parenthesis and ends with the matching right parenthesis. If the last clause applied was (2), then \(\theta\) is \(\neg \psi\), and the induction hypothesis applies to \(\psi\). Similarly, if the last clause applied was (6) or (7), then \(\theta\) consists of a quantifier, a variable, and a formula to which we can apply the induction hypothesis. It follows that the Lemma holds for \(\theta\).