# Proof by induction on wffs

Here is an extra problem form Enderton: Let $\alpha$ be a formula in sentential logic. Prove that there is some tautologically equivalent formula in which negation (if it occurs at all) is applied only to sentence symbols.

I realize that the proof is by induction. First, if $\alpha$ is a sentence symbol, then it's equivalent to itself, in which negation does not occur at all. So the base case holds.

But I'm unsure about the inductive steps.

First, suppose $\alpha = (\neg \beta)$ for some sentence $\beta$ that is equivalent to some sentence in which negation (if it occurs) is only applied to sentence symbols. How do I now show that $\alpha$ satisfies the property we want.

Second, suppose $\alpha = (\alpha_1 \square \alpha_2)$ where $\square \in \{\land, \vee, \rightarrow, \leftrightarrow\}$ and $\alpha_1$ and $\alpha_2$ satisfy the desired property. How do I show that $\alpha$ now satisfies it?

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$.

• How does it follow by induction that $\neg \gamma$ and $\neg \delta$ have the desired property? Can't we just conclude that $\gamma$ and $\delta$ have it? Commented Mar 11, 2017 at 2:36
• @CuriousKid7 A proof by induction on complexity of formula operates by showing the claim for all formulas of a given complexity at each step. When we consider $\neg\beta$, we are working on the formulas with complexity $n+1$, where $\beta$ has complexity $n$; that means we've already shown the claim for complexity $n$. As subformulas of $\beta$, $\gamma$ and $\delta$ have complexity at most $n - 1$, so $\neg\gamma$ and $\neg\delta$ have complexity at most $n$, putting them within the collection of formulas for which we've already proven the claim. Commented Mar 11, 2017 at 3:50
• I see. How is complexity of a formula defined? Also, in the general framework of induction, what is the base set, sentence symbols still? And what are the operations being used--conjunction, negation, etc.? Commented Mar 11, 2017 at 4:11
• @CuriousKid7 You may want to review the relevant definitions in Enderton - look at any proof by induction on formulas for an example. Complexity of formula is defined inductively: sentence symbols have complexity zero, and each operator ($\neg$,$\wedge$, etc.) increases the complexity by one. The base case is complexity zero, which is sentence symbols. The operations you already listed in your original question. Commented Mar 11, 2017 at 4:18
• @CuriousKid7 No, that's never true, of course. I'm saying $\neg\alpha$ satisfies the condition as well (for $\alpha$ complexity zero, $\alpha$ itself is the desired formula). You'll notice that in my induction step, I didn't consider the case in which $\alpha$ is $\neg\beta$ and $\beta$ is a sentence symbol; that's because I handled it in the base case. Commented Mar 11, 2017 at 17:25