Bounty edit: As comments below point out, I do seem to have a fundamental misunderstanding of what has been asked and the idea of induction on length of derivation. Trouble is, I have studied the textbook and the comments again and again and I still have no idea how to go about doing this question. I have only one example on induction on derivation length on a deduction theorem proof so I am kinda desperate. Please if anyone can offer 1) a concrete solution, or 2) a hint on how to proceed, I will be very grateful.
Please if anyone can offer a concrete solution, or a hint on how to proceed, I will be very grateful.
Could anyone check my working please? Also could anyone explain why is mathematical induction needed please? Why isn't a conventional proof possible?
If we can derive $Γ\vdash φ$ and we replace all occurrences of the variable $p$ in $φ$ and the formulas in the set $Γ$ by a formula $θ$, turning $φ$ into the formula $φ'$ and the set $Γ$ into the set $Γ'$, then we can derive $Γ'\vdashφ'$. Use the method of mathematical induction on the length of a derivation to prove this result.
Strategy: Prove that, for each line $\alpha_i$ of proof of $Γ\vdash φ$, $Γ'\vdash \alpha_i$. Since the last line of $\alpha_i$ is $φ$, successfully proving that this applies to the entire proof will prove that $Γ'\vdash φ'$.
Base cases: $\alpha_i$ being 1) an axiom, 2) an assumption.
1): We can use an axiom anywhere in the proof, so the fact that $Γ$ changed into $Γ'$ doesn't matter: we can still derive $\alpha_i$.
2): Since $\alpha_i$ is an assumption from the original set $Γ$, we simply do the replacement of formulas in the set $Γ$ by a formula $θ$ so that we get $Γ'$, and $\alpha_i$ follows naturally from $Γ'$.
Inductive step: the only case left is when $\alpha_i$ is derived from using modus ponens from prior lines. Let our inductive hypothesis be that all prior lines satisfy the property.
If we are able to use MP, it must be the case that there are two prior lines where $\phi \to \alpha_i$ and $\phi$. But since they are prior lines, they must have already fulfilled the criteria, ie. $Γ'\vdash \phi \to \alpha_i$ and $Γ'\vdash \phi$. Therefore by using the Cut theorem we get $Γ'\vdash \alpha_i$.
I assume that you are working with (a) a propositional language with letters $p,q,\dots$ and connectives $\neg$ and $\to$; (b) a set of axioms which are "all instances" of some specified set of the formulas (c) a single rule of inference MP, that is from $\Gamma\vdash (\alpha\to\beta)$ and $\Gamma\vdash\alpha$ deduce $\Gamma\vdash\beta$.
The first thing is to be clear that the function $\gamma\mapsto\gamma'$ is well-defined on the set of formulas. This is easy, because the formulas are defined recursively, and we have unique readability: hence the map can recursively defined by $p':=\theta$, $q':=q$ if $q$ is a propositional letter other than $p$, and then $(\neg\alpha)':=(\neg\alpha')$, $(\alpha\to\beta)':=(\alpha'\to\beta')$. We can then, for any set of formulas $\Delta$, put $\Delta':=\{\delta' | \delta\in\Delta\}$.
We now need a simple observation: If $\alpha$ is the instance of an axiom so is $\alpha'$. To see this it does not matter what the axioms are precisely, we just need the recursive definition of $\gamma'$.
Now suppose we know that $\Gamma\vdash\phi$. That means we have a sequence of formulas $(\alpha_1,\dots,\alpha_k=\phi)$ where for each $i$ we have one of
(a) $\alpha_i\in\Gamma$;
(b) $\alpha_i$ is an instance of an axiom;
(c) (MP step) there exist $i_1,i_2<i$ with $\alpha_{i_1}=\beta$, $\alpha_{i_2}=(\beta\to\alpha_i)$.
We now assert that the sequence $(\alpha'_1,\dots,\alpha'_k=\phi')$ is a derivation of $\Gamma'\vdash\phi'$.
To see this we note that
(a) if $\alpha_i\in\Gamma$ then $\alpha'_i\in\Gamma'$;
(b) if $\alpha_i$ is an instance of an axiom then so is $\alpha'_i$;
(c) if there exist $i_1,i_2<i$ with $\alpha_{i_1}=\beta$, $\alpha_{i_2}=(\beta\to\alpha_i)$ then there exist $i_1,i_2<i$ (the same ones!) with $\alpha'_{i_1}=\beta'$, $\alpha'_{i_2}=(\beta\to\alpha_i)'$, and as we observed $(\beta\to\alpha_i)'=(\beta'\to\alpha'_i)$, so this is a proper MP step.
(We could write this as an induction but there is no need since the derivation of $\phi$ translates line-for-line into a derivation of $\phi'$.