×

Four variables suffice. (English) Zbl 1168.03013

From the introduction: What I wish to propose in the present paper is a new form of ‘career induction’ for ambitious young logicians. In this case, the induction proceeds downward rather than upward. The basic problem is this: if we look at the \(n\)-variable fragments of relevant propositional logics, at what point does undecidability begin? Let’s focus, to be definite, on the logic \(\mathbf R\). J. K. Slaney [J. Symb. Log. 50, 487–501 (1985; Zbl 0576.03015)] showed that the 0-variable fragment of \(\mathbf R\) (where we allow the sentential constants \(t\) and \(f\)) contains exactly 3088 non-equivalent propositions, and so is clearly decidable. In the opposite direction, I claimed in my paper of 1984 [J. Symb. Log. 49, 1059–1073 (1984; Zbl 0581.03011)] that the five-variable fragment of \(\mathbf R\) is undecidable. The proof given there was sketchy (to put the matter charitably), and a close examination reveals that although the result claimed is true, the proof given is incorrect (something that escaped even the eagle eye of the Maximum Leader of the Logicians Liberation League). In the present paper, I give a detailed and (I hope) correct proof that the four-variable fragments of the principal relevant logics are undecidable. This leaves open the question of the decidability of the \(n\)-variable fragments for \(n=1,2,3\). At what point does undecidability set in?

MSC:

03B47 Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics)
03B25 Decidability of theories and sets of sentences
03D35 Undecidability and degrees of sets of sentences
PDFBibTeX XMLCite