Decidability of the admissibility problem in layer-finite logics
type: Item
instance of: scholarly article
title: Decidability of the admissibility problem in layer-finite logics
zbMATH Open document ID: 0576.03012
DOI: 10.1007/BF01979701
published in: Algebra and Logic
publication date: 1984-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/187258
review text: The aim of the paper is to study admissible rules of inference in layer- finite propositional modal logics. Let \(\lambda\) be a modal propositional logic containing S4 and eq(\(\lambda)\) be the variety of closure algebras (or, dually, interior algebras) corresponding to \(\lambda\). Among the logics of fixed layer n, the smallest (weakest) logic is \(S4+\delta_ n\). The following statements are proved: (1) The universal theory of free algebras of the variety \(eq(S4+\delta_ n)\) is decidable for any \(n<\omega\). (As corollary it follows that the admissibility problem in each logic \(S4+\delta_ n\) has an affirmative answer: there exists an algorithm which for each rule decides whether it is admissible or not.) (2) The quasivariety generated by the free algebras of infinite rank in the variety \(eq(S4+\delta_ n)\) has no basis of quasiidentities in a finite number of variables for \(n\geq 2\). (It follows that all logics \(S4+\delta_ n\) for \(n\geq 2\) have no finite basis of admissible rules.) (3) The elementary theory of the free algebras of the variety \(eq(S4+\delta_ n)\) is completely undecidable for any \(2\leq n<\omega.\) Remark: author proved analogous results for the modal system S4 and the intuitionistic propositional logic H. These results are published in Algebra Logika 23, No.5, 546-572 (1984) and ibid. 24, No.1, 87-107 (1985). In particular, the admissibility problem for H is decidable - positive solution of problem 40 of \textit{H. Friedman} [One hundred and two problems in mathematical logic, J. Symb. Logic 40, 113-129 (1975; Zbl 0318.02002)].
Mathematics Subject Classification ID: 03B45
Mathematics Subject Classification ID: 03B25
zbMATH DE Number: 3920441
zbMATH Keywords: admissible rules of inference
zbMATH Keywords: layer-finite propositional modal logics
zbMATH Keywords: closure algebras
zbMATH Keywords: interior algebras
zbMATH Keywords: free algebras
zbMATH Keywords: quasiidentities
author: Vladimir Rybakov
MaRDI profile type: Publication
cites work: Q3950540
cites work: ON ADMISSIBLE RULES OF INTUITIONISTIC PROPOSITIONAL LOGIC
cites work: Q5582306
OpenAlex ID: W2062047612
description: scientific article; zbMATH DE number 3920441