I am reading the book "A Friendly Introduction To Mathematical Logic". In one of the proofs they use induction, but I am not sure how this induction step is done. Could you please help me?
First I will post a definition:
Then I will post the proof with the induction step, I have highlighted this in red:
Could you please tell me how the induction step is done? I don't see why we have that $\gamma \in \Gamma$ is an element of C?
On
This is a special case of a more general phenomenon.
Let $M$ be a set, and let $\mathcal{F}$ be a set of functions from $M^k$ to $M$, where the so-called "arity" $k$ can depend on the function. Let $A\subseteq M$.
We say a subset $S$ of $M$ is $\mathcal{F}$-closed if $A\subseteq S$, and whenever $f$ is an $k$-ary function in $\mathcal{F}$ and $x_1,\ldots x_k\in S$, then also $f(x_1,\ldots,x_k)\in S$.
A construction sequence is a sequence $y_1,\ldots,y_n$ such that for each $y_i$, either $y_i\in A$, or $y_i=f(y_{j_1},\ldots,y_{j_k})$ with each $j_l<i$ and $f\in\mathcal{F}$.
Let $\overline{A}$ be the intersection of all the $\mathcal{F}$-closed sets, $\overline{A}=\bigcap_{S\text{ is }\mathcal{F}\text{-closed}}S$. (Obviously $M$ is $\mathcal{F}$-closed, so the intersection has a least one $S$ in it.) Clearly $\overline{A}$ is the smallest $\mathcal{F}$-closed set.
Theorem: $\overline{A}$ is the set $A_\infty$ of all $y$'s that can appear as the last element of a construction sequence.
Proof: First we show $A_\infty\subseteq\overline{A}$ by induction on the length of construction sequences. Suppose for any construction sequence of length $m<n$, that its last element belongs to $\overline{A}$. Let $y_1,\ldots,y_n$ be a construction sequence. By inductive hypothesis, each $y_m$ with $m<n$ belongs to $\overline{A}$. By the definition of construction sequence, either $y_n\in A$, in which case $y_n\in\overline{A}$ because $\overline{A}$ is $\mathcal{F}$-closed, or $y_n=f(y_{j_1},\ldots,y_{j_k})$ with each $j_l<n$, and hence $y_{j_l}\in\overline{A}$ by what was just said about $y_m$ with $m<n$. But then $y_n\in\overline{A}$, again because $\overline{A}$ is $\mathcal{F}$-closed.
In the other direction, it's easy to see that $A_\infty$ is $\mathcal{F}$-closed. So it's one of the "intersectands" in the definition of $\overline{A}$ and so $\overline{A}\subseteq A_\infty$. QED
Now to apply this to the case at hand, we let $A=\Lambda\cup\Sigma$, $M$ be the set of all formulas, and note that each rule of inference is an $n$-ary function from formulas to formulas, for some $n$.
The proof works even if we replace $\mathcal{F}$ with a set of relations. Instead of demanding $y_i=f(y_{j_1},\ldots,y_{j_k})$ with $f\in\mathcal{F}$ in the definition of construction sequence, we demand $R(y_{j_1},\ldots,y_{j_k},y_i)$ with $R\in\mathcal{F}$.
In this generalized form, the theorem applies to, say, closures of all kinds in algebra (e.g., the closure of a subset of a field under the field operations, or the algebraic closure of a subset of an algebraically closed field). If you generalize even further by allowing "infinitary" relations (i.e., relations that are subsets of $P(M)\times M$, where $P(M)$ is the power-set of $M$), then it has examples in general topology and analysis.
For the second question, you have to understand that $\Gamma$ is just a set of formulas (which you can imagine as the premises of your rule of inference).
For the first question, the idea is to do induction on the structure of the formulas in $\Sigma$. Remember that whenever you want to prove some property for an inductively defined set (as is the case for you set $\Sigma$ of deductions), you first prove the property for the base objects of the set (in your case, the logical and nonlogical axioms), and then move on to the objects generated by the production rules of the inductive set (that is, the rules that take elements in the set and form new elements that are still in the set, in your case all the possible inference rules, where the premises are the initial object). This are all the ways that an object can be created according to the inductive definition, so it follows that the property holds for the entire set.
Now, for the inductive step, an inductively generated object in $\Sigma$ is going to be of the form $(\Gamma, \phi)$. Your inductive hypothesis becomes $\Gamma \subset C$ (as always, it says that the inputs to the production rule satisfy the property you want to prove). Remember $\Gamma$ is just a set of formulas. But now by the third point of the definition of $C$, $\phi$ is in $C$, and you are done.
It can take a bit of time to get used to structural induction, so do not worry