Prove by induction that if $\varphi$ is justified with reference to a rule of inference $(\Gamma,\varphi)$, then $\varphi\in C$

Question

I have to prove by induction the last part of Proposition 2.2.4 in C. Leary's "A Friendly Introduction to Mathematical Logic". The proposition states that the set $Thm_\Sigma$ is the smallest set $C$ such that $\Sigma\subset C$, $\Lambda\subset C$, and if $(\Gamma,\varphi)$ is a rule of inference and $\Gamma\subset C$, then $\varphi\in C$. I began my induction proof by showing that if there exists a one-line deduction of $\varphi$ from $\Gamma$, then $\varphi$ is an axiom and therefore in $C$ by part 2. Next I assumed that $\varphi\in C$ given there exists a deduction of length less than $n$. Now I want to show that $\varphi\in C$ given there exists a deduction of length $n$ but am not sure how to proceed. Any hint would be greatly appreciated.

Answer 1

[Proposition 2.2.4. ] makes two separate claims about the set $\text {Thm}_{\Sigma}$. The first claim is that $\text {Thm}_{\Sigma}$ satises the three criteria. The second claim is that $\text {Thm}_{\Sigma}$ is the smallest set to satisfy the criteria."

Your quetion regards the second part.

The proof of the second claim amounts to showing that $\text {Thm}_{\Sigma}$ is the smallest set satisfying the criteria, i.e. that it is included in every set that satisfies the criteria.

This in turn amounts to showing that if $C$ is a collection of formulas satisfying the given requirements, then $\text {Thm}_{\Sigma} \subseteq C$.

So, we assume that $C$ is a class whatever satisfying the conditions, and we have to show that every element of $\text {Thm}_{\Sigma}$ is in $C$.

$\text {Thm}_{\Sigma} = \{ \phi \mid \Sigma \vdash \phi \}$, and thus if $\phi \in \text {Thm}_{\Sigma}$, there is a deduction from $\text {Thm}_{\Sigma}$ with last line $\phi$.

If $\phi$ is justied by virtue of being either a logical or nonlogical axiom [i.e. a member of $\text {Thm}_{\Sigma}$], then $\phi$ is explicitly included in the set $C$, because by assumption $C$ satisfies criteria 1 and 2.

The last case is when $\phi$ is justied by reference to a rule of inference $(\Gamma, \phi)$. Here we need a proof by induction.

The induction is on the lenght $n$ of the derivation of $\phi$.

We assume that the claim holds for derivations of lenght less than $n$; this means that for each $\gamma \in \Gamma$ used in the application of the rule $(\Gamma, \phi)$ we already know that they belong to $C$, because they are part of the derivation, and so they are already in $\text {Thm}_{\Sigma}$ with derivations of lenght less than $n$ and we have assumed that the claim holds in this case.

So $\phi$ is justified by way of $(\Gamma, \phi)$ where for every $\gamma \in \Gamma$ we have $\gamma \in C$. But this means $\Gamma \subseteq C$ and so we can apply the 3rd criteria to conclude with: $\phi \in C$.

Conclusion: we have showed that, for every $\phi$, if $\phi \in \text {Thm}_{\Sigma}$, then $\phi \in C$, and this amount to:

$\text {Thm}_{\Sigma} \subseteq C$.

But $C$ is a "generic" class satisfying the three conditions; thus, we can "generalize" concluding that the result hold for every $C$ satisfying the conditions.

And thus, if $\text {Thm}_{\Sigma}$ is included in every $C$, then it is included in the intersection of all $C$s, i.e. it is the smallest set satisfying the criteria.