# About a proof of the Adequacy of Natural Deduction for Propositional Logic

In Mathematical Logic by Chiswell and Hodges, section 3.10 page 89 proves the following theorem:

Theorem 3.10.1 (Adequacy of Natural Deduction for Propositional Logic)

Let $$\Gamma$$ be a set of formulas of $$\text{LP}(\sigma)$$ and $$\psi$$ a formula of $$\text{LP}(\sigma)$$. If $$\Gamma\models_\sigma\psi$$ then $$\Gamma\vdash_\sigma\psi$$.

Before moving to the proof of the lemmas for the theorem as well as the theorem itself, the authors said:

Although what was said looks natural to me by intuition, I tried to find a mathematical justification: Why is it true that if $$\Gamma\vdash_\sigma\psi$$ and $$\psi \,\,eq\,\,\phi$$ (which means $$\psi$$ is logically equivalent to $$\phi$$) then $$\Gamma\vdash_\sigma\phi$$ ?

Proving this property (call it (*)) would justify that we can indeed use the stripped-down version of $$\text{LP}$$, because in this case, if we prove Theorem 3.10.1 for formulas of $$\text{LP}$$ which contains only $$\land$$,$$\lnot$$ and $$\perp$$ as truth functions, then if $$\psi\in\text{LP}(\sigma)$$ then we can take a logically equivalent formula to it, call it $$\phi$$, which contains only $$\land$$,$$\lnot$$ and $$\perp$$ as truth functions, and then apply Theorem 3.10.1 to $$\phi$$ (note that since $$\psi\,\,eq\,\,\phi$$, we have $$\Gamma\models_\sigma\psi$$ if and only if $$\Gamma\models_\sigma\phi$$), we would have $$\Gamma\vdash_\sigma\phi$$ and thus, using (*), we would conclude that $$\Gamma\vdash_\sigma\psi$$.

Note that (*) is correct as it's easy to see that it's a corollary of Theorem 3.10.1 along with the Soundness of Natural Deduction for Propositional Logic Theorem, which was already proven in section 3.9. To avoid a circular proof, I have to prove (*) without using that theorem. I wrote an argument that I couldn't complete unless I prove that any tautology $$\phi\in\text{LP}(\sigma)$$ satisfies $$\vdash_\sigma\phi$$ (again that's a corollary of Theorem 3.10.1), which I failed to prove using induction on the complexity of $$\phi$$.

As the authors said, we can leave the other truth function symbols of $$\text{LP}$$ and enlarge the proof to take them into consideration, but I'm curious about how we can rigorously avoid that. Could you please help me?

To avoid circularity, you have to take the "longer way", i.e. enlarge Definition 3.10.4 of Hintikka set to consider all the connectives, and consider all cases in Lemma 3.10.5 and Lemma 3.10.6: it is longer but straightforward.

A "standard" approach in many textbook would be: avoiding the shortcut, consider only some "typical" cases (like $\land$, $\lnot$ and $\bot$) and leave the others to the reader as an exercise.

The alternative, but not in the "spirit" of natural deduction, is to start with a restricted set of connectives and introduce the others as abbreviation: $P \lor Q$ as $\lnot (\lnot P \land \lnot Q)$, etc.

Of course, the rules for the defined connectives must be derived from the primitive rules.

• Thank you very much for your answer! Looking at $P\lor Q$ as an abbreviation of $\lnot(\lnot P\land\lnot Q)$ instead of an equivalent of it is a really good idea! But as you said, that's not in the spirit of Natural Deduction and doesn't seem straightforward for me (being a beginner in Mathematical Logic, especially that many things would change). For the standard approach (given as an exercise at the end of the section), could you please verify if the following definition of a Hintikka set would work fine? Jun 10, 2016 at 15:25
• We say that a set $\Gamma$ of formulas of $\text{LP}$ is a Hintikka set (for $\text{LP}$) if it has the following properties: (1) If a formula $(\phi\land\psi)$ is in $\Gamma$ then $\phi$ is in $\Gamma$ and $\psi$ is in $\Gamma$. (2) If a formula $(\phi\lor\psi)$ is in $\Gamma$ then at least one of $\phi$ and $\psi$ is in $\Gamma$. (3) If a formula $(\lnot(\lnot\phi))$ is in $\Gamma$ then $\phi$ is in $\Gamma$. (4) If a formula $\phi\to\psi$ is in $\Gamma$ then at least one of $(\lnot \phi)$ and $\psi$ is in $\Gamma$. Jun 10, 2016 at 15:25
• (5) If a formula $(\phi\leftrightarrow\psi)$ is in $\Gamma$ then either $\phi$ and $\psi$ are in $\Gamma$ or $(\lnot\psi)$ and $(\lnot\phi)$ are in $\Gamma$. (6) $\perp$ is not in $\Gamma$. (7) There is no propositional symbol $p$ such that both $p$ and $(\lnot p)$ are in $\Gamma$. Jun 10, 2016 at 15:32
• @Scientifica - very good ! Jun 10, 2016 at 20:06
• By the way, while solving exercise 3.10.1, I figured out that the above definition of a Hintikka set isn't making it easy to extend the proof of Lemma 3.10.5 as given in the book, so I added the following conditions to a Hintikka set: (8) If a formula $(\not(\phi\land\psi))$ is in $\Gamma$ then at least one of $\not\phi$ and $\not\psi$ is in $\Gamma$. (9) If a formula $(\lnot(\phi\lor\psi))$ is in $\Gamma$ then $\lnot\phi$ and $\lnot\psi$ are both in $\Gamma$. ...and so on for $\to$ and $\leftrightarrow$. Jun 10, 2016 at 21:25

If |=($\psi$ eq $\phi$), and ($\Gamma$ $\vdash$ $\psi$), then

|=($\psi$ eq $\phi$) and ($\Gamma$ |= $\psi$) by soundness.

|=($\psi$ eq $\phi$) implies that |=($\psi$ $\rightarrow$ $\phi$).

|=($\psi$ $\rightarrow$ $\phi$) implies ($\psi$ |= $\phi$).

Thus can infer that ($\Gamma$ |= $\psi$) and ($\psi$ |= $\phi$).

So, we can infer ($\Gamma$ |= $\phi$).

Now by completeness ($\Gamma$ |- $\phi$).

As another argument, note that you have the rule of inference

($\phi$ <-> $\psi$) $\vdash$ ($\phi$ -> $\psi$).

If we have two formulas logically equivalent we have |=($\phi$ <-> $\psi$). By completeness we have $\vdash$($\phi$ <-> $\psi$). And thus we can obtain ($\phi$ -> $\psi$ and the result you mentioned above.

• Thank you for your answer! However, I have to prove (*) without using the Adequacy Theorem (thus without using one side of the completeness theorem). However, you used it. That would make the proof of this theorem circular. Jun 10, 2016 at 17:10
• @Scientifica Why do you have to prove it without using the Adequacy Theorem? Note that the authors of your text did not claim the result you've cited before proving the Adequacy Theorem, did they? Additionally, it could get proved by proving that if ($\alpha$ eq $\beta$) then wherever $\alpha$ appears as a subformula in a provable formula F, then F', which is just like F except that $\alpha$ has gotten replaced by $\beta$ at one of the spots where $\alpha$ appears, also comes as provable. I think Kleene does this in Introduction to Metamathematics, but for a different system. Jun 10, 2016 at 18:29
• Thank you for your reply. The reason why I can't use the Adequacy Theorem is that (*) is what I need, as explained in my question, to prove the Adequacy Theorem, but indeed it can be proved using it. Jun 10, 2016 at 18:33