# 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
Full Text:
##### References:
  Bloom, S.L.; Brown, J.D.; Suszko, R., Some theorems on abstract logics, Bull. acad. polon. sci., 19, 333-335, (1970) · Zbl 0217.01402  Cohn, P.M., Universal algebra, (1965), New York  Dummet, M.; Lemmon, E., Modal logic between S4 and S5, Z. math. logik grundlag. math., 5, 250-264, (1969) · Zbl 0178.30801  Fine, K., An incomplete logic containing S4, Theoria, 40, 1, 23-29, (1974) · Zbl 0287.02011  Friedman, H., One hundred and two problems in mathematical logic, J. symbolic logic, 40, 113-130, (1975) · Zbl 0318.02002  Grigolia, R.Sh., The free S4.3-algebras, (), 281-286, (in Russian)  Harrop, R., Concerning formulas of the types A → B ∨ C, A → ∃xb(x), J. symbolic logic, 25, 27-32, (1960) · Zbl 0098.24201  Jonsson, B.; Tarski, B.; Tarski, A., Boolean algebras with operators, Amer. J. math., 23, 891-939, (1951) · Zbl 0045.31505  Kripke, S., Semantical analysis of modal logic, Z. math. logik grundlag. math., 9, 67-96, (1963) · Zbl 0118.01305  Lemmon, E.; Lemmon, E., Algebraic semantic for modal logics I, II, J. symbolic logic, J. symbolic logic, 31, 191-218, (1966) · Zbl 0147.24805  Los, J., The algebraic treatment of the methodology of elementary deductive systems, Studia logica, 2, 151-212, (1955) · Zbl 0067.25101  Los, J.; Suszko, R., Remarks on sentential logic, Indagationes math., 20, 177-183, (1958) · Zbl 0092.24802  Maksimova, L.L.; Rybakov, V.V., On the lattice of normal modal logic, Algebra i logika, 15, 188-216, (1974), (in Russian)  McKinsey, J.; Tarski, A., Some theorems about the sentential calcull of Lewis and Heyting, J. symbolic logic, 13, 1-15, (1948) · Zbl 0037.29409  Mints, G.E., Admissible and derivable rules of inference, Zap. nauch. semin. LOMI AN SSSR, 8, 189-191, (1968), (in Russian)  Mints, G.E., Derivability of admissible rules, Zap. nauch, semin. LOMIN AN SSSR, 32, 85-89, (1972) · Zbl 0358.02031  Rybakov, V.V., Admissible rules of pretabular modal logics, Algebra i logika, 20, 440-464, (1981), (in Russian) · Zbl 0489.03005  Rybakov, V.V., Admissible rules for logics containing S4.3, Siberian math. J., 25, 5, 141-145, (1984), (in Russian) · Zbl 0582.03009  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  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  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  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  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  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  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  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)  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  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  Segerberg, K., An essay in classical modal logic, Vols 1-3, (1971), Filosofiska studier Uppsala · Zbl 0311.02028  Shehtman, V.B., Rieger-Nishimura’s ladders, Dokl. akad. nauk SSSR, 240, 3, 549-552, (1978), (in Russian)  Suszko, R., Concerning the method of logical schemes, Studia logica, 11, 185-214, (1961) · Zbl 0121.25209  Thomasson, S.K., Semantical analysis of tense logics, J. symbolic logic, 37, 150-158, (1972) · Zbl 0238.02027  Thomasson, S.K., An incompleteness theorem in modal logic, Theoria, 40, 1, 30-34, (1974) · Zbl 0287.02012  Tsitkin, A.I., On the admissible rules for intuitionistic propositional calculus, Math. USSR sbornik, 102, 2, 314-323, (1977), (in Russian) · Zbl 0386.03011  Tsitkin, A.I., On structure-complete intermediate logics, Dokl. acad. sci. SSSR, 241, 4, 40-43, (1978), (in Russian) · Zbl 0412.03009  Tsitkin, A.I., Author’s summary of Candidate’s dissertation, Institute of mathematics with computer center akad. sci. MSSR, (1979), Kishinev · Zbl 0422.03035  Tsitkin, A.I., On the admissibility of rules in the intuitionistic calculus, Semiotics and informatics, 12, 59-61, (1979), (in Russian)  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.