×

zbMATH — the first resource for mathematics

Multiple conclusion rules in logics with the disjunction property. (English) Zbl 06751231
Artemov, Sergei (ed.) et al., Logical foundations of computer science. International symposium, LFCS 2016, Deerfield Beach, FL, USA, January 4–7, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9537, 76-89 (2016).
Summary: We prove that for the intermediate logics with the disjunction property any basis of admissible rules can be reduced to a basis of admissible m-rules (multiple-conclusion rules), and every basis of admissible m-rules can be reduced to a basis of admissible rules. These results can be generalized to a broad class of logics including positive logic and its extensions, Johansson logic, normal extensions of \(\mathsf {S4}\), n-transitive logics and intuitionistic modal logics.
For the entire collection see [Zbl 1364.03006].
MSC:
03B70 Logic in computer science
PDF BibTeX Cite
Full Text: DOI arXiv
References:
[1] Belnap Jr., N.D., Leblanc, H., Thomason, R.H.: On not strengthening intuitionistic logic. Notre Dame J. Formal Log. 4, 313–320 (1963) · Zbl 0131.00605
[2] Bezhanishvili, G.: Varieties of monadic heyting algebras. I. Stud. Logica 61(3), 367–402 (1998) · Zbl 0964.06008
[3] Cabrer, L., Metcalfe, G.: Admissibility via natural dualities. J. Pure Appl. Algebra 219(9), 4229–4253 (2015) · Zbl 1346.08005
[4] Chagrov, A., Zakharyaschev, M.: Modal Logic. Oxford Logic Guides. The Clarendon Press, vol. 35. Oxford University Press, Oxford Science Publications, New York (1997) · Zbl 0871.03007
[5] Chagrov, A., Zakharyashchev, M.: The disjunction property of intermediate propositional logics. Stud. Log. 50(2), 189–216 (1991) · Zbl 0739.03016
[6] Chagrov, A.V.: A decidable modal logic for which the admissibility of inference rules is an undecidable problem. Algebra i Logika 31(1), 83–93 (1992) · Zbl 0782.03005
[7] Citkin, A.: A note on admissible rules and the disjunction property in intermediate logics. Arch. Math. Logic 51(1–2), 1–14 (2012) · Zbl 1248.03047
[8] Craig, W.: On axiomatizability within a system. J. Symb. Log. 18, 30–32 (1953) · Zbl 0053.20101
[9] Fedorishin, B.R.: An explicit basis for the admissible inference rules in the Gödel-Löb logic GL. Sibirsk. Mat. Zh. 48, 423–430 (2007). (In Russian) · Zbl 1164.03302
[10] Friedman, H.: One hundred and two problems in mathematical logic. J. Symb. Log. 40, 113–129 (1975) · Zbl 0318.02002
[11] Goudsmit, J.: A note on extensions: admissible rules via semantics. In: Artemov, S., Nerode, A. (eds.) LFCS 2013. LNCS, vol. 7734, pp. 206–218. Springer, Heidelberg (2013) · Zbl 1437.03105
[12] Goudsmit, J.: Intuitionistic Rules Admissible Rules of Intermediate Logics. Ph.D. thesis, Utrech University (2015)
[13] Goudsmit, J.P., Iemhoff, R.: On unification and admissible rules in Gabbay-de Jongh logics. Ann. Pure Appl. Log. 165(2), 652–672 (2014) · Zbl 1316.03016
[14] Harrop, R.: Concerning formulas of the types \[ A\rightarrow B\bigvee C,\, A\rightarrow (Ex)B(x) \]
in intuitionistic formal systems. J. Symb. Log. 25, 27–32 (1960) · Zbl 0098.24201
[15] Iemhoff, R.: On the admissible rules of intuitionistic propositional logic. J. Symb. Log. 66(1), 281–294 (2001) · Zbl 0986.03013
[16] Iemhoff, R.: Intermediate logics and Visser’s rules. Notre Dame J. Formal Log. 46(1), 65–81 (2005) · Zbl 1102.03032
[17] Iemhoff, R.: On the rules of intermediate logics. Arch. Math. Log. 45(5), 581–599 (2006) · Zbl 1096.03025
[18] Jeřábek, E.: Admissible rules of modal logics. J. Log. Comput. 15(4), 411–431 (2005) · Zbl 1077.03011
[19] Jeřábek, E.: Independent bases of admissible rules. Log. J. IGPL 16(3), 249–267 (2008) · Zbl 1146.03008
[20] Jeřábek, E.: Canonical rules. J. Symb. Log. 74(4), 1171–1205 (2009) · Zbl 1186.03045
[21] Kleene, S.C.: Introduction to Metamathematics. D. Van Nostrand Co. Inc., New York (1952) · Zbl 0047.00703
[22] Kracht, M.: Book review of [37]. Notre Dame J. Form. Log. 40(4), 578–587 (1999)
[23] Kracht, M.: Modal consequence relations, chap. 8. In: Blackburn, P., et al. (eds.) Handbook of Modal Logic. Studies in Logic and Practical Reasonong, vol. 3, pp. 491–545. Elsevier, New York (2007)
[24] Lorenzen, P.: Einführung in die operative Logik und Mathematik. Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen mit besonderer Berücksichtigung der Anwendungsgebiete, Bd. LXXVIII. Springer, Berlin-Göttingen-Heidelberg (1955)
[25] Lorenzen, P.: Protologik. Ein Beitrag zum Begrndungsproblem der Logik. Kant-Studien 47, 1–4, Januay 1956, pp. 350–358. Translated in Lorenzen, P., Constructive Philosophy, 59–70. Univerisity of Massachusettes Press, Amherst (1987)
[26] Mints, G.: Derivability of admissible rules. J. Sov. Math. 6 (1976), 417–421. Translated from Mints, G. E. Derivability of admissible rules. (Russian) Investigations in constructive mathematics and mathematical logic, V. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 32, pp. 85–89 (1972)
[27] Muravitsky, A.: Logic KM: a biography. In: Bezhanishvili, G. (ed.) Leo Esakia on Duality in Modal and Intuitionistic Logics. Outstanding Contributions to Logic, vol. 4, pp. 155–185. Springer, Netherlands (2014) · Zbl 1350.03015
[28] Novikov, P. S.: Konstruktivnaya matematicheskaya logika s tochki zreniya klassicheskoi [Constructive mathematical logic from the point of view of classical logic]. Izdat. ”Nauka”, Moscow (1977) With a preface by S. I. Adjan, Matematicheskaya Logika i Osnovaniya Matematiki. [Monographs in Mathematical Logic and Foundations of Mathematics] (in Russian)
[29] Odintsov, S., Rybakov, V.: Unification and admissible rules for paraconsistent minimal Johanssons’ logic \[ \mathbf{J} \]
and positive intuitionistic logic \[ \mathbf{IPC}^+ \]
. Ann. Pure Appl. Logic 164(7–8), 771–784 (2013) · Zbl 1323.03029
[30] Pogorzelski, W.A.: Structural completeness of the propositional calculus. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 19, 349–351 (1971) · Zbl 0214.00704
[31] Prucnal, T.: Structural completeness of Medvedev’s propositional calculus. Rep. Math. Logic 6, 103–105 (1976) · Zbl 0358.02024
[32] Roziére, P.: Régles admissibles en calcul propositionnel intuitionniste. Ph.D. thesis, Université Paris VII (1992)
[33] Rybakov, V.V.: A criterion for admissibility of rules in the modal system S4 and intuitionistic logic. Algebra i Logika 23(5), 546–572 (1984) · Zbl 0598.03013
[34] Rybakov, V. V.: Bases of admissible rules of the modal system Grz and intuitionistic logic. Mat. Sb. (N.S.) vol. 128(170), 3, pp. 321–338, 446 (1985)
[35] Rybakov, V.V.: Problems of admissibility and substitution, logical equations and restricted theories of free algebras. In: Logic, methodology and philosophy of science, VIII (Moscow, 1987), vol. 126. Stud. Logic Found. Math., pp. 121–139. North-Holland, Amsterdam (1989)
[36] Rybakov, V.V.: Admissibility of rules of inference, and logical equations in modal logics that axiomatize provability. Izv. Akad. Nauk SSSR Ser. Mat. 54, 357–377 (1990). (In Russian)
[37] Rybakov, V.V.: Admissibility of Logical Inference Rules. Studies in Logic and the Foundations of Mathematics, vol. 136. North-Holland Publishing Co., Amsterdam (1997) · Zbl 0872.03002
[38] Rybakov, V.V., Terziler, M., Gencer, C.: Unification and passive inference rules for modal logics. J. Appl. Non-Class. Log. 10(3–4), 369–377 (2000) · Zbl 1040.03014
[39] Rybakov, V.V.: Construction of an explicit basis for rules admissible in modal system S4. MLQ Math. Log. Q. 47(4), 441–446 (2001) · Zbl 0992.03027
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.