# Induction in the proof of soundness theorem

The statement of the soundness theorem in both propositional and predicate logic is as follows:

$\Sigma \vdash \alpha \rightarrow \Sigma \vDash \alpha$ for $\Sigma \subseteq W, \alpha \in W$ where $W$ is the set of well formed formulas of our language, and suppose that our axiom system is $T$, the set of all tautologies. I want to prove the theorem, and it seems the most common tactic (and has been suggested to me) is to use induction on the length of $\alpha.$ Since $\Sigma \vdash \alpha$, there must have been some deduction sequence $(\alpha_1,\alpha_2,\alpha_3,....\alpha_n=\alpha)$ for $\alpha_i \in \Sigma$. Then, each $\alpha_i$ has arisen from one of the following:

1. $\alpha_i$ was part of the hypotheses,
2. $\alpha_i$ is a tautology
3. $\alpha_i$ followed from an earlier $\alpha_j$ by the way of modus ponens.

If $\alpha$ falls into one of the first 2 categories we are finished. Then through the process of elimination we want to use induction should $\alpha$ occur as the result of modus ponens. How exactly is this accomplished? It seems that there are many ways for $\alpha_i$ to follow as a result of modus ponens - perhaps it is the result of $\alpha_j \rightarrow \alpha_i$, or perhaps $\alpha_j \iff \alpha_i$ or maybe even $(\alpha_k \rightarrow \alpha_j) \rightarrow \alpha_i$. How many cases are there?

• NO; only one way. If $\alpha_i$ is in the proof sequence by way of mp, we nust have $\alpha_j$ and $\alpha_k$ in the sequence such that $\alpha_k= \alpha_j \to \alpha_i$. – Mauro ALLEGRANZA Oct 13 '17 at 6:10
• Thus, by induction hypo, $\Sigma \vDash \alpha_j$ and $\Sigma \vDash \alpha_k$. – Mauro ALLEGRANZA Oct 13 '17 at 6:11
• "to use induction on the length of the derivation of $α$". – Mauro ALLEGRANZA Oct 13 '17 at 7:24

As Mauro suggests, the induction works on the length of the derivation of $\alpha$. In other words, the induction happens on the number of steps of the proof of the (well-formed) formula.
3. Follow by the use of modus ponens from previous steps in the sequence. Now, the previous steps would be some conditional and the antecedent of that conditional. But, by the induction hypothesis, since they are previous steps, both are tautologies. And when A and (A$\rightarrow$B) are tautologies, so is B. B is the new step in this case. Since all previous steps were tautologies, and the new step is also a tautology, it follows that all members of the proof are tautologies.
That covers all possible cases. Therefore, by induction on the length of the derivation of the formula $\alpha$, the soundness meta-theorem follows.