×

zbMATH — the first resource for mathematics

Problems of substitution and admissibility in the modal system Grz and in intuitionistic propositional calculus. (English) Zbl 0709.03009
Summary: Questions connected with the admissibility of rules of inference and the solvability of the substitution problem for modal and intuitionistic logic are considered in an algebraic framework. The main result is the decidability of the universal theory of the free modal algebra \({\mathcal F}_{\omega}(Grz)\) extended in signature by adding constants for the free generators. As corollaries we obtain: (a) there exists an algorithm for the recognition of admissibility of rules with parameters (hence also without them) in the modal system Grz, (b) the substitution problem for Grz and for the intuitionistic calculus H is decidable, (c) intuitionistic propositional calculus H is decidable with respect to admissibility (a positive solution of Friedman’s problem). A semantical criterion for the admissibility of rules of inference in Grz is given.

MSC:
03B45 Modal logic (including the logic of norms)
03B20 Subsystems of classical logic (including intuitionistic logic)
03B25 Decidability of theories and sets of sentences
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bloom, S.L.; Brown, J.D.; Suszko, R., Some theorems on abstract logics, Bull. acad. polon. sci., 19, 333-335, (1970) · Zbl 0217.01402
[2] Cohn, P.M., Universal algebra, (1965), New York
[3] Dummet, M.; Lemmon, E., Modal logic between S4 and S5, Z. math. logik grundlag. math., 5, 250-264, (1969) · Zbl 0178.30801
[4] Fine, K., An incomplete logic containing S4, Theoria, 40, 1, 23-29, (1974) · Zbl 0287.02011
[5] Friedman, H., One hundred and two problems in mathematical logic, J. symbolic logic, 40, 113-130, (1975) · Zbl 0318.02002
[6] Grigolia, R.Sh., The free S4.3-algebras, (), 281-286, (in Russian)
[7] Harrop, R., Concerning formulas of the types A → B ∨ C, A → ∃xb(x), J. symbolic logic, 25, 27-32, (1960) · Zbl 0098.24201
[8] Jonsson, B.; Tarski, B.; Tarski, A., Boolean algebras with operators, Amer. J. math., 23, 891-939, (1951) · Zbl 0045.31505
[9] Kripke, S., Semantical analysis of modal logic, Z. math. logik grundlag. math., 9, 67-96, (1963) · Zbl 0118.01305
[10] Lemmon, E.; Lemmon, E., Algebraic semantic for modal logics I, II, J. symbolic logic, J. symbolic logic, 31, 191-218, (1966) · Zbl 0147.24805
[11] Los, J., The algebraic treatment of the methodology of elementary deductive systems, Studia logica, 2, 151-212, (1955) · Zbl 0067.25101
[12] Los, J.; Suszko, R., Remarks on sentential logic, Indagationes math., 20, 177-183, (1958) · Zbl 0092.24802
[13] Maksimova, L.L.; Rybakov, V.V., On the lattice of normal modal logic, Algebra i logika, 15, 188-216, (1974), (in Russian)
[14] McKinsey, J.; Tarski, A., Some theorems about the sentential calcull of Lewis and Heyting, J. symbolic logic, 13, 1-15, (1948) · Zbl 0037.29409
[15] Mints, G.E., Admissible and derivable rules of inference, Zap. nauch. semin. LOMI AN SSSR, 8, 189-191, (1968), (in Russian)
[16] Mints, G.E., Derivability of admissible rules, Zap. nauch, semin. LOMIN AN SSSR, 32, 85-89, (1972) · Zbl 0358.02031
[17] Rybakov, V.V., Admissible rules of pretabular modal logics, Algebra i logika, 20, 440-464, (1981), (in Russian) · Zbl 0489.03005
[18] Rybakov, V.V., Admissible rules for logics containing S4.3, Siberian math. J., 25, 5, 141-145, (1984), (in Russian) · Zbl 0582.03009
[19] Rybakov, V.V., The decidability of the problem of admissibility in finite-layer modal logics, Algebra i logika, 23, 100-116, (1984), (in Russian) · Zbl 0576.03012
[20] Rybakov, V.V., A criterion of admissibility of rules in the modal system S4 and in intuitionistic logic, Algebra i logika, 23, 546-572, (1984), English transl. in Algebra and Logic (1984) · Zbl 0598.03013
[21] Rybakov, V.V., The bases of admissible rules for logics S4 and int, Algebra i logika, 24, 87-107, (1985), English transl. in Algebra and Logic (1985) · Zbl 0598.03014
[22] Rybakov, V.V., The elementary theories of free topo-Boolean and pseudo-Boolean algebras, Matemat. zametki, 37, 6, 797-802, (1985), (in Russian) · Zbl 0593.03041
[23] Rybakov, V.V., A criterion for admissibility rules of inference in modal and intuitionistic logic, Soviet math. dokl., 32, 2, 452-455, (1985) · Zbl 0596.03025
[24] Rybakov, V.V., The bases of admissible rules for modal system grz and intuitionistic logic, Math. USSR sborbnik, 56, 2, 311-331, (1987) · Zbl 0617.03007
[25] Rybakov, V.V., Equations in a free topo-Boolean algebra and the substitution problem, Soviet math. dokl., 33, 2, 428-431, (1986) · Zbl 0607.06008
[26] Rybakov, V.V., The equations in a free topo-Boolean algebra, Algebra i logika, 25, 2, 172-204, (1986), English transl. in Algebra and Logic (1986)
[27] Rybakov, V.V., Decidability of admissibility in the modal system grz and intuitionistic logic, Math. USSR izvestiya, 28, 3, 589-608, (1987) · Zbl 0624.03009
[28] Rybakov, V.V., An algorithm for the recognition of admissibility of rules of inference in the modal system G, (), 175-177, Section: algorithms of difficult problems
[29] Segerberg, K., An essay in classical modal logic, Vols 1-3, (1971), Filosofiska studier Uppsala · Zbl 0311.02028
[30] Shehtman, V.B., Rieger-Nishimura’s ladders, Dokl. akad. nauk SSSR, 240, 3, 549-552, (1978), (in Russian)
[31] Suszko, R., Concerning the method of logical schemes, Studia logica, 11, 185-214, (1961) · Zbl 0121.25209
[32] Thomasson, S.K., Semantical analysis of tense logics, J. symbolic logic, 37, 150-158, (1972) · Zbl 0238.02027
[33] Thomasson, S.K., An incompleteness theorem in modal logic, Theoria, 40, 1, 30-34, (1974) · Zbl 0287.02012
[34] Tsitkin, A.I., On the admissible rules for intuitionistic propositional calculus, Math. USSR sbornik, 102, 2, 314-323, (1977), (in Russian) · Zbl 0386.03011
[35] Tsitkin, A.I., On structure-complete intermediate logics, Dokl. acad. sci. SSSR, 241, 4, 40-43, (1978), (in Russian) · Zbl 0412.03009
[36] Tsitkin, A.I., Author’s summary of Candidate’s dissertation, Institute of mathematics with computer center akad. sci. MSSR, (1979), Kishinev · Zbl 0422.03035
[37] Tsitkin, A.I., On the admissibility of rules in the intuitionistic calculus, Semiotics and informatics, 12, 59-61, (1979), (in Russian)
[38] Wojcitski, R., Some remarks on the consequence operation in sentential logics, Fund. math., 58, 269-279, (1970) · Zbl 0206.27401
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.