×

zbMATH — the first resource for mathematics

Decidability of the admissibility problem in layer-finite logics. (English. Russian original) Zbl 0576.03012
Algebra Logic 23, 75-87 (1984); translation from Algebra Logika 23, No. 1, 100-116 (1984).
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 H. Friedman [One hundred and two problems in mathematical logic, J. Symb. Logic 40, 113-129 (1975; Zbl 0318.02002)].

MSC:
03B45 Modal logic (including the logic of norms)
03B25 Decidability of theories and sets of sentences
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] Yu. L. Ershov, Problems of Decidability and Constructive Models [in Russian], Nauka, Moscow (1980).
[2] L. L. Maksimova, ”Modal logics of finite layers,” Algebra Logika,14, No. 3, 304–319 (1975).
[3] L. L. Maksimova and V. V. Rybakov, ”The lattice of normal modal logics,” Algebra Logika,13, No. 2, 188–216 (1974).
[4] A. I. Mal’tsev, Algebraic Systems [in Russian], Nauka, Moscow (1970).
[5] V. V. Rybakov, ”Admissible rules for pretable modal logics,” Algebra Logika,20, No. 4, 440–464 (1981). · Zbl 0489.03005
[6] A. I. Tsitkin, ”Admissible rules for the intuitionistic predicate logic,” Mat. Sb.,102, No. 2, 289–301 (1977). · Zbl 0386.03011
[7] T. Hosoi, ”On intermediate logics. I”, J. Fac. Sci. Univ. Tokyo,I, No. 14, 293–312 (1967). · Zbl 0188.31602
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.