Career induction for quantifiers.
Robert K. Meyer · Notre Dame Journal of Formal Logic · 1980
In [7], I showed that Belnap's method of "career induction" comes to an unexpected halt at the second degree.While the halt was called for relevant logics, the method is quite general.What it amounts to, roughly, is that for a large number of logical systems, one can find, for each formula A in the vocabulary, a formula A* such that: (i) A* is of the second degree and (ii) A is provable in the system iff ^4* is provable therein.Thus, for example, if we could find a decision procedure for the second-degree formulas of R, we could solve the decision question for all of R. (This question is open.)The purpose of the present note is to generalize the method, with the particular aim of showing that first-order relevant logics are also second-degree reducible.Again, the method remains quite general, so that the decision to apply it to the analysis of R x and its kin may be written off to an idiosyncratic interest of the author.It is to be hoped that readers with other problems will not be put off by this interest.It often happens, in logical analysis, that iteration of some particles is held to increase the complexity of a formula, whereas other particles lead to no such increase.Thus, for example, iterated occurrences of D in modal logic are held to increase the "degree of modal involvement", whereas iterated occurrences of particles like & and ~, being merely truth-functional, do not increase degree.It is very easy to tie numbers to this scheme.For illustrative purposes, consider a sentential logic formulated with just two rc-ary connectives c and C, of which c is to be thought of as degree-nonincreasing and C as degreeincreasing.Then a sensible and familiar specification of the degree of a formula is the following.The degree of every propositional variable p shall be 0. The degree of c(A u . . .9 A n ) shall be the greatest among the degrees of A u . .., A n .And the degree of C(A X , . .., A n ) shall be one greater than the maximal degree of the Aj.It is easy to see that what this scheme measures is the depth of nesting of the degree-raising connective C among the formulas A of our sample language.