I'm currently trying to make my way through the basic metatheory of FOL reading Shapiro's entry on Classical Logic in SEP.
Since I encounter difficulties in understanding proof procedures, I took a look at The Logic Book ( by Bergmann) which is recommended in the Bibliography ( at the end of Shapiro's article).
Note : Here is an example of the kind of proof I can find in Shapiro's text ( https://plato.stanford.edu/entries/logic-classical/#FeatSynt)
Lemma 2. Each formula consists of a string of zero or more unary markers followed by either an atomic formula or a formula produced using a binary connective, via one of clauses (3)–(5).
Proof: We proceed by induction on the complexity of the formula or, in other words, on the number of formation rules that are applied. The Lemma clearly holds for atomic formulas. Let n be a natural number, and suppose that the Lemma holds for any formula constructed from n or fewer instances of clauses (2)–(7). Let θ be a formula constructed from n+1 instances. The Lemma holds if the last clause used to construct θ was either (3), (4), or (5). If the last clause used to construct θ was (2), then θ is ¬ψ. Since ψ was constructed with n instances of the rule, the Lemma holds for ψ (by the induction hypothesis), and so it holds for θ. Similar reasoning shows the Lemma to hold for θ if the last clause was (6) or (7). By clause (8), this exhausts the cases, and so the Lemma holds for θ, by induction.
- In The Logic Book, I can read this
" We may now generally charaterize arguments by mathematical induction. In such an argument, we arrange the items about which we want to prove some thesis in a series of groups . In our example we arranged the sentences of Sentential Logic into the series : all sentences contaning 0 occurrence of connectives, all sentences containing 1 occurrences..., all sentences containing 2 occurrence... Having arranged the items in such a series , an argument by mathematical induction then takes the following form:
(1) the thesis holds for every member of the first group of the series
(2) For each group of the series, if the thesis holds for every member of every prior group, then it holds for every member of that group as well.
(3) Therefore, the thesis holds for every member of every group in the series."
My question(s) :
(1) is this the method applied by Shapiro in his proof of " lemma 2" ( reproduced above)?
(2) In The Logic Book, the method is termed " strong induction" ; does Shapiro use rather structural induction? ( Is " induction on the compelxity of a formula" structural inducton or strong induction, or ordinary induction? )
(3) In the inductive hypothesis of Shapiro's proof, how to understand the " OR FEWER" part? If Shapiro applied stong induction, and if - in this method - the inductive hypothesis is that the thesis ( or property) holds for every group prior to the $n^{th}$ group, shouldn't we find instead " for any formula constructed from $n$ AND fewer instances of clauses (2)–(7)"
(4) also, induction hypothesis in the template ( in he Logic Book) seems to go from group $1$, $2$, $3$ , $n-1$ to group $n$ , while Shapiro goes from $1$, $2$, $3$ , $n$ to $n+1$.
(5) In case you had any reading recommendation regarding the uses of induction ( strong? structural? ) and proof methods in the metalogic of FOL , I'd be very pleased.
