Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-09T20:01:19.315Z Has data issue: false hasContentIssue false
  • English
  • Français

Canonical rules

Published online by Cambridge University Press:  12 March 2014

Emil Jeřábek
Emil Jeřábek*
Affiliation:
Institute of Mathematics. As Cr Žitná 25, 115 67 Praha 1, Czech Republic, E-mail: [email protected] URL: http://math.cas.cz/~jerabek/index.html
Get access Rights & Permissions [Opens in a new window]

Abstract

We develop canonical rules capable of axiomatizing all systems of multiple-conclusion rules over K4 or IPC, by extension of the method of canonical formulas by Zakharyaschev [37]. We use the framework to give an alternative proof of the known analysis of admissible rules in basic transitive logics, which additionally yields the following dichotomy: any canonical rule is either admissible in the logic, or it is equivalent to an assumption-free rule. Other applications of canonical rules include a generalization of the Blok–Esakia theorem and the theory of modal companions to systems of multiple-conclusion rules or (unitary structural global) consequence relations, and a characterization of splittings in the lattices of consequence relations over monomodal or superintuitionistic logics with the finite model property.

Keywords

Inference rulemodal logicintermediate logicadmissible rule
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 74 , Issue 4 , December 2009 , pp. 1171 - 1205
Copyright
Copyright © Association for Symbolic Logic 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Baader, Franz and Narendran, Paliath, Unification of concept terms in description logics, Journal of Symbolic Computation, vol. 31 (2001), pp. 277–305.CrossRefGoogle Scholar
[2] Blackburn, Patrick, van Benthem, Johan, and Wolter, Frank (editors), Handbook of modal logic, Studies in Logic and Practical Reasoning, vol. 3, Elsevier, Amsterdam, 2007.Google Scholar
[3] Blok, Willem J., Varieties of interior algebras, Ph.D. thesis, University of Amsterdam, 1976.Google Scholar
[4] Blok, Willem J., On the degree of incompleteness in modal logics and the covering relation in the lattice of modal logics, Technical Report 78-07, Department of Mathematics, University of Amsterdam, 1978.Google Scholar
[5] Chagrov, Alexander V., A decidable modal logic with the undecidable admissibility problem for inference rules, Algebra and Logic, vol. 31 (1992), no. 1, pp. 53–55.CrossRefGoogle Scholar
[6] Chagrov, Alexander V. and Zakharyaschev, Michael, Modal logic, Oxford Logic Guides, vol. 35, Oxford University Press, 1997.CrossRefGoogle Scholar
[7] W. Wistar Comfort and Stylianos Negrepontis, The theory of ultrafilters, Die Grundlehren der mathematischen Wissenschaften, vol. 211, Springer, Berlin, 1974.Google Scholar
[8] Esakia, Leo L., To the theory of modal and superintuitionistic systems, Logical inference. Proceedings of the USSR symposium on the theory of logical inference (Smirnov, V. A., editor), Nauka, Moscow, 1979, pp. 147–172 (Russian).Google Scholar
[9] Fine, Kit, An ascending chain of SA logics, Theoria, vol. 40 (1974), no. 2, pp. 110–116.CrossRefGoogle Scholar
[10] Fine, Kit, Logics containing K4, Part 11, this Journal, vol. 50 (1985), no. 3, pp. 619–651.Google Scholar
[11] Friedman, Harvey M., One hundred and two problems in mathematical logic, this Journal, vol. 40 (1975), no. 2, pp. 113–129.Google Scholar
[12] Ghilardi, Silvio, Unification in intuitionistic logic, this Journal, vol. 64 (1999), no. 2, pp. 859–880.Google Scholar
[13] Ghilardi, Silvio, Best solving modal equations, Annals of Pure and Applied Logic, vol. 102 (2000), no. 3, pp. 183–198.CrossRefGoogle Scholar
[14] Iemhoff, Rosalie, On the admissible rules of intuitionistic propositional logic, this Journal, vol. 66 (2001), no. 1, pp. 281–294.Google Scholar
[15] Iemhoff, Rosalie, Intermediate logics and Visser's rules, Notre Dame Journal of Formal Logic, vol. 46 (2005), no. 1, pp. 65–81.CrossRefGoogle Scholar
[16] Iemhoff, Rosalie, On the rules of intermediate logics, Archive for Mathematical Logic, vol. 45 (2006), no. 5, pp. 581–599.CrossRefGoogle Scholar
[17] Jankov, V. A., The relationship between deducibility in the intuitionistic propositional calculus and finite implicational structures, Mathematics of the USSR, Doklady, vol. 4 (1963), no. 4, pp. 1203–1204.Google Scholar
[18] Jeřábek, Emil, Admissible rules of modal logics, Journal of Logic and Computation, vol. 15 (2005), no. 4, pp. 411–431.CrossRefGoogle Scholar
[19] Jeřábek, Emil, Frege systems for extensible modal logics, Annals of Pure and Applied Logic, vol. 142 (2006), pp. 366–379.CrossRefGoogle Scholar
[20] Jeřábek, Emil, Complexity of admissible rules, Archive for Mathematical Logic, vol. 46 (2007), no. 2, pp. 73–92.CrossRefGoogle Scholar
[21] Jeřábek, Emil, independent bases of admissible rules, Logic Journal of the IGPL, vol. 16 (2008), no. 3, pp. 249–267.CrossRefGoogle Scholar
[22] Katětov, Miroslav, A theorem on mappings, Commentationes Mathematicae Universitatis Carolinae, vol. 8 (1967), no. 3, pp. 432–433.Google Scholar
[23] Kracht, Marcus, An almost general splitting theorem for modal logic, Stadia Logica, vol. 49 (1990), no. 4, pp. 455–470.CrossRefGoogle Scholar
[24] Kracht, Marcus, Review of [29], >Notre Dame Journal of Formal Logic, vol. 40 (1999), no. 4, pp. 578–587.Google Scholar
[25] Kracht, Marcus, Modal consequence relations, In Blackburn et al. [2], pp. 491–545.CrossRefGoogle Scholar
[26] Lorenzen, Paul, Einführung in die operative Logik und Mathematik, Grundlehren der mathematischen Wissenschaften, vol. 78, Springer, 1955 (German).CrossRefGoogle Scholar
[27] Maksimova, Larisa L. and Rybakov, Vladimir V., Lattices of modal logics, Algebra and Logic, vol. 13 (1974), pp. 105–122.CrossRefGoogle Scholar
[28] Rautenberg, Wolfgang, Splitting lattices of logics, Archiv für mathematische Logik und Grundlagenforschung, vol. 20 (1980), no. 3-4, pp. 155–159.CrossRefGoogle Scholar
[29] Rybakov, Vladimir V., Admissibility of logical inference rules, Studies in Logic and the Foundations of Mathematics, vol. 136, Elsevier, 1997.CrossRefGoogle Scholar
[30] Rybakov, Vladimir V., Logical consecutions in discrete linear temporal logic, this Journal, vol. 70 (2005), no. 4, pp. 1137–1149.Google Scholar
[31] Rybakov, Vladimir V., Logical consecutions in intransitive temporal linear logic of finite intervals, Journal of Logic and Computation, vol. 15 (2005), no. 5, pp. 663–678.CrossRefGoogle Scholar
[32] Rybakov, Vladimir V., Linear temporal logic with Until and Before on integer numbers, deciding algorithms, Computer science-theory and applications (Grigoriev, Dima, Harrison, John, and Hirsch, Edward A., editors), Lecture Notes in Computer Science, vol. 3967, Springer, 2006, pp. 322–333.CrossRefGoogle Scholar
[33] Wolter, Frank, Tense logic without tense operators, Mathematical Logic Quarterly, vol. 42 (1996), no. 1, pp. 145–171.CrossRefGoogle Scholar
[34] Wolter, Frank and Zakharyaschev, Michael, Modal decision problems, In Blackburn et al. [2], pp. 427–489.CrossRefGoogle Scholar
[35] Wolter, Frank and Zakharyaschev, Michael, Undecidability of the unification and admissibility problems for modal and description logics, ACM Transactions on Computational Logic, vol. 9 (2008), no. 4.CrossRefGoogle Scholar
[36] Zakharyaschev, Michael, Modal companions of superintuitionistic logics: syntax, semantics, and preservation theorems, Mathematics of the USSR, Sbornik, vol. 68 (1991), no. 1, pp. 277–289.CrossRefGoogle Scholar
[37] Zakharyaschev, Michael, Canonical formulas for K4. Part I: Basic results, this Journal, vol. 57 (1992), no. 4, pp. 1377–1402.Google Scholar
[38] Zakharyaschev, Michael, Canonical formulas for K4. Part IT. Cofinalsubframe logics, this Journal, vol. 61 (1996), no. 2, pp. 421–449.Google Scholar
[39] Zakharyaschev, Michael, Canonical formulas for K4. Part III: the finite model property, this Journal, vol. 62 (1997), no. 3, pp. 950–975.Google Scholar