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

Question

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?

Answer 1

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.

Answer 2

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.