The second step is trivial - $\alpha$ has no negations that weren't in $\alpha_1$ and $\alpha_2$. So any negation in $\alpha$ is in either $\alpha_1$ or $\alpha_2$; and any negation in $\alpha_1$ or $\alpha_2$ is applied only to sentence symbols.

In the first case, there are several sub-cases. Suppose $\beta$ is just a sentence symbol - then we're done. Suppose instead that $\beta$ is of the form $\gamma \wedge \delta$. Then $\neg\beta = \neg(\gamma \wedge \delta) \equiv \neg\gamma \vee \neg\delta$. Since $\gamma$ and $\delta$ are of strictly lower complexity than $\beta$, by induction $\neg\gamma$ and $\neg\delta$ have the desired property, so $\neg\gamma\vee\neg\delta$ does as well.

I'll let you work out the other sub-cases for yourself - they'll be similar.

EDIT: In more detail:

A wff has complexity zero if it is a sentence symbol. If $\alpha$ has complexity $n$, then $\neg\alpha$ has complexity $n+1$. The complexity of $\beta\square\gamma$ for $\square$ a connective is $1+n$, where $n$ is the maximum of the complexities of $\beta$ and $\gamma$.

We prove by induction on complexity of formula that every wff is equivalent to a wff in which negations apply only to sentence symbols.

The case of complexity zero is trivial: if $\alpha$ has complexity zero, $\alpha$ is a sentence symbol, so $\neg\alpha$ is a wff in which negations apply only to sentence symbols.

Suppose now that the claim is true for wffs of complexity at most $n$, and let $\alpha$ be a wff of complexity $n+1$. Then $\alpha$ takes one of the forms $\neg\beta$, $\gamma\wedge\delta$, $\gamma\vee\delta$, etc.

Suppose $\alpha$ is $\gamma\square\delta$ for some connective $\square$. $\gamma$ and $\delta$ both have complexity at most $n$, since $\alpha$ has complexity $n+1$; so by the induction hypothesis, $\gamma$ and $\delta$ are equivalent to wffs $\gamma'$ and $\delta'$ respectively so that in each negations only apply to sentence symbols. Then $\gamma'\square\delta'$ is equivalent to $\alpha$ and has the desired property.

Suppose instead that $\alpha$ is $\neg\beta$. Then $\beta$ has complexity $n$. If $\beta$ is of the form $\neg\gamma$, then $\gamma$ has complexity less than $n$, so has an equivalent formula $\gamma'$ with the desired property; but $\gamma'$ is equivalent to $\alpha$, so we're done.

On the other hand, if $\beta$ takes the form (for example) $\gamma\wedge\delta$, then $\gamma$ and $\delta$ each have complexity less than $n$. $\neg(\gamma\wedge\delta) \equiv \neg\gamma\vee\neg\delta$, by DeMorgan's laws. $\neg\gamma$ has complexity one more than that of $\gamma$; but $\gamma$ had complexity strictly less than $n$, so $\neg\gamma$ has complexity at most $n$. Therefore, by the induction hypothesis, $\neg\gamma$ is equivalent to a wff $\gamma'$ in which negation applies only to sentence symbols. Likewise, $\neg\delta$ has an equivalent wff $\delta'$ of the desired sort. Then $\gamma'\vee\delta'$ is equivalent to $\alpha$, and has the desired property.

It remains to show the induction for the connectives $\vee$, $\to$, and $\leftrightarrow$.

## Best Answer

You can see some textbooks, like :

Herbert Enderton, A Mathematical Introduction to Logic (2nd ed - 2001),

SECTION 1.4 : Induction and Recursion, page 34-onDirk van Dalen, Logic and Structure (5th ed - 2013), page 7-on :

We call an application of Theorem 2.1.3 a

proof by induction on$\varphi$.[...]

[...]

[...]

For a formalization into set theory, see :

and the final remark [page 93] :