×

zbMATH — the first resource for mathematics

The undecidability of the disjunction property of propositional logics and other related problems. (English) Zbl 0799.03009
The paper proves undecidability for many general properties of intermediate and modal propositional logics (above S4), and also some other interesting results related to the disjunction property. The method of undecidability proofs is based on simulating Minsky machines in Kripke models [cf. L. A. Chagrova, ibid. 56, No. 4, 1261-1272 (1991; Zbl 0737.03018)] and on some earlier ideas of the first author [Algebra Logika 29, No. 3, 350-367 (1990; Zbl 0723.03005) and ibid., No. 5, 613-623 (1990; Zbl 0729.03009)]. It is proved that decidability and the finite model property are undecidable for normal modal calculi extending Grzegorczyk logic Grz (Theorems 1 and 2).
Then the authors prove sufficient conditions for the disjunction property (DP) of intermediate logics and Halldén-completeness (HC) of extensions of Grz; they are formulated in terms of “canonical formulas” introduced by the second author [Dokl. Akad. Nauk SSSR 269, 18-22 (1983; Zbl 0548.03009)]. They show that HC is not necessarily preserved for model companions (Theorem 5) and construct a modal logic with DP which lacks HC (Theorem 6) and a continuum of extensions of Grz with HC which lack DP (Theorem 6), and of those with both HC and DP. Also they prove undecidability of DP and of HC for calculi extending Grz. The axiomatizability of a given calculus by formulas of some special types (e.g. by implicative formulas in the intermediate case) turns out to be undecidable as well.
The last two sections study “Maksimova-completeness” and discuss some open problems.

MSC:
03B45 Modal logic (including the logic of norms)
03B55 Intermediate logics
03D35 Undecidability and degrees of sets of sentences
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1007/BF00370331 · Zbl 0766.03015 · doi:10.1007/BF00370331
[2] DOI: 10.1002/malq.19590051405 · Zbl 0178.30801 · doi:10.1002/malq.19590051405
[3] Semiotics and Informatics 15 pp 74– (1980)
[4] DOI: 10.1007/BF00370182 · Zbl 0739.03016 · doi:10.1007/BF00370182
[5] Soviet Mathematics Doklady 240 pp 549– (1978)
[6] An undecidable problem in correspondence theory 56 pp 1261– (1991) · Zbl 0737.03018
[7] Mathematical problems of cybernetics (1993)
[8] An essay in classical modal logic 13 (1971)
[9] Mathematicheskie Zametki 51 pp 117– (1992)
[10] The mathematics of metamathematics (1963)
[11] Algebra and Logic 29 pp 350– (1990)
[12] Some results on the intermediate logics 8 pp 117– (1972) · Zbl 0253.02022
[13] On formulas of one variable in intuitionistic propositional calculus 25 pp 327– (1960) · Zbl 0108.00302
[14] DOI: 10.1305/ndjfl/1093870446 · Zbl 0487.03008 · doi:10.1305/ndjfl/1093870446
[15] DOI: 10.2307/1970290 · Zbl 0105.00802 · doi:10.2307/1970290
[16] DOI: 10.1002/malq.19720180802 · Zbl 0246.02020 · doi:10.1002/malq.19720180802
[17] DOI: 10.1007/BF00373276 · Zbl 0634.03021 · doi:10.1007/BF00373276
[18] Algebra and Logic 13 pp 188– (1974)
[19] DOI: 10.1007/BF01881550 · Zbl 0635.03019 · doi:10.1007/BF01881550
[20] Algebra and Logic 18 pp 556– (1979)
[21] Undecidability of the completeness problem of modal logic 9 pp 341– (1982)
[22] DOI: 10.1007/BF00370479 · Zbl 0435.03021 · doi:10.1007/BF00370479
[23] Algebra and Logic 16 pp 643– (1977)
[24] Algebra and Logic 15 pp 168– (1976)
[25] Algebra and Logic 11 pp 558– (1972)
[26] The decidability of certain intermediate logics 33 pp 258– (1968) · Zbl 0175.27103
[27] Bulletin of the American Mathematical ociety 55 pp 50– (1949)
[28] Algebra and Logic 2 pp 47– (1963)
[29] DOI: 10.1007/BF01988049 · Zbl 0079.00702 · doi:10.1007/BF01988049
[30] Notre Dame Journal of Formal Logic (1993)
[31] Canonical formulas for K4. Part I: Basic results 57 pp 1377– (1992) · Zbl 0774.03005
[32] Soviet Mathematics Doklady 8 pp 1203– (1963)
[33] Mathematicheskiĭ Sbornik 180 pp 1415– (1989)
[34] Proceedings of 8th USSR Conference ”Logic and Methodology of Science”, Vilnius pp 35– (1982)
[35] Reports on Mathematical Logic 6 pp 41– (1976)
[36] Algebra and Logic 28 pp 402– (1989)
[37] Proceedings of IV Soviet-Finland Symposium for Mathematical Logic, Tbilisi pp 81– (1988)
[38] Algebra and logic 27 pp 659– (1988)
[39] A sequence of decidable finitely axiomatizable intermediate logics with the disjunction property 39 pp 67– (1974) · Zbl 0289.02032
[40] Mathematicheskie Zametki 42 pp 729– (1987)
[41] The decidability of the Kreisel-Putnam system 35 pp 431– (1970)
[42] Soviet Mathematics Doklady 29 pp 252– (1984)
[43] Logics containing K4. Part II 50 pp 619– (1985) · Zbl 0574.03008
[44] Soviet Mathematics Doklady 27 pp 274– (1983)
[45] Theoria 40 pp 110– (1974)
[46] Reports on Mathematical Logic 2 pp 63– (1974)
[47] Study on non-classical logics and set theory pp 257– (1979)
[48] Reports on Mathematical Logic 1 pp 39– (1973)
[49] Mathematicheskiĭ Sbornik 102 pp 289– (1977)
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.