×

Pure extensions, proof rules, and hybrid axiomatics. (English) Zbl 1115.03009

Hybrid modal (formal) languages are modal (formal) languages having the expressive power to name possible worlds, asserting equalities between worlds, and describing accessibility relations. In this paper, the authors examine three different kinds of hybrid languages for propositional modal logic and one kind of hybrid language for first-order quantified modal logic; they also characterize semantic systems for all of these kinds of languages. These systems are possible worlds semantics in the fashion of Kripke’s semantics, with additional clauses accommodating the syntactic peculiarities of the hybrid languages considered. For each kind of hybrid modal languages, axiomatic formal systems are presented by the authors. Some of these systems contain, among others, certain non-orthodox proof rules; these rules are widely discussed in the paper. Strong completeness theorems are proved for the two axiomatic systems formulated for the most expressive sort of the hybrid propositional logic languages (considered by the authors). For the other axiomatic systems, strong completeness theorems are rather proved for extensions of the systems by means of certain kinds of rules and/or axioms with respect to models satisfying the frame properties defined by those same rules and/or axioms. The completeness proofs are Henkin proofs and differ, in this way, from the standard modal approach by means of canonical models. It is important to point out that, as a result of the expressive power of the hybrid languages, the completeness results cover frame classes that are not definable in orthodox modal languages.

MSC:

03B45 Modal logic (including the logic of norms)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Areces, C., P. Blackburn, and M. Marx, ’Hybrid logics: Characterization, interpolation and complexity’, Journal of Symbolic Logic, 66(3):977–1010, 2001. · Zbl 0984.03018 · doi:10.2307/2695090
[2] Areces, C., P. Blackburn, and M. Marx, ’Repairingthe interpolation theorem in quantified modal logic’, Annals of Pure and Applied Logics, 123(1–3):287–299, 2003. · Zbl 1031.03025 · doi:10.1016/S0168-0072(03)00059-9
[3] Areces, C., and B. ten Cate, ’Hybrid logics’, in P. Blackburn, J. van Benthem, and F.Wolter (eds), Handbook of Modal Logic, volume 3 of Studies in Logic and Practical Reasoning, Elsevier, 2006, pp. 821–868.
[4] Bezhanishvili, N. , and B. ten Cate, ’Transfer results for hybrid logic, Part 1: the case without satisfaction operators’, Journal of Logic and Computation, 16:177–197, 2006. · Zbl 1101.03019 · doi:10.1093/logcom/exi056
[5] Blackburn, P., ’Internalizing labelled deduction’, Journal of Logic and Computation, 10:137–168, 2000. · Zbl 0953.03018 · doi:10.1093/logcom/10.1.137
[6] Blackburn, P., ’Arthur Prior and hybrid logic’, Synthese, 150:329–372, 2006. · Zbl 1108.03001 · doi:10.1007/s11229-005-5512-y
[7] Blackburn, P., M. de Rijke, and Y. Venema, Modal logic, Cambridge University Press, Cambridge, UK, 2001. · Zbl 0988.03006
[8] Blackburn, P., and M. Marx, ’Constructive interpolation in hybrid logic’, Journal of Symbolic Logic, 68(2):463–480, 2003. · Zbl 1059.03020 · doi:10.2178/jsl/1052669059
[9] Blackburn, P., and J. ’Seligman, Hybrid languages’, Journal of Logic, Language and Information, 4:251–272, 1995. · Zbl 0847.03009 · doi:10.1007/BF01049415
[10] Blackburn, P., and B. ten Cate, ’Beyond pure axioms: Node creating rules in hybrid tableaux’, in C. Areces, P. Blackburn, M. Marx, and U. Sattler (eds.), Hybrid Logics, July 25 2002, pp. 21–35.
[11] Blackburn, P., and M. Tzakova, ’Hybrid languages and temporal logic’ (full version), Technical report, Universität des Saarlandes, Saarbräcken, 1998. CLAUS-Report 96. · Zbl 0904.03009
[12] Blackburn, P., and M. Tzakova, ’Hybrid languages and temporal logic’, Logic Journal of the IGPL, 7(1):27–54, 1999. · Zbl 0920.03029 · doi:10.1093/jigpal/7.1.27
[13] Braöner, T.. ’Natural deduction for hybrid logic’, Journal of Logic and Computation, 14(3):329–353, 2004. · Zbl 1060.03036 · doi:10.1093/logcom/14.3.329
[14] Bull, R., ’An approach to tense logic’, Theoria, 36:282–300, 1970. · Zbl 0227.02012 · doi:10.1111/j.1755-2567.1970.tb00428.x
[15] Buss, S., ’Bounded arithmetic and propositional proof complexity’, in H. Schwichtenberg (ed.), Logic and Computation, Springer, 1997, pp. 67–122. · Zbl 0882.68130
[16] de Rijke, M., ’The modal logic of inequality’, Journal of Symbolic Logic, 57(2):566–584, 1992. · Zbl 0788.03019 · doi:10.2307/2275293
[17] Feferman, S., ’Persistent and invariant formulas for outer extensions’, Compositio Mathematica, 20:29–52, 1968. · Zbl 0162.01601
[18] Feferman, S., and Kreisel G., ’Persistent and invariant formulas relative to theories of higher order’, Bulletin of the American Mathematical Society, 72:480–485, 1966. · Zbl 0234.02038 · doi:10.1090/S0002-9904-1966-11507-0
[19] Fine, K., ’An incomplete logic containing S4’, Theoria, 40:23–29, 1974. · Zbl 0287.02011 · doi:10.1111/j.1755-2567.1974.tb00076.x
[20] Gargov, G., and V. Goranko, ’Modal logic with names’, Journal of Philosophical Logic, 22:607–636, 1993. · Zbl 0793.03012 · doi:10.1007/BF01054038
[21] Goranko, V., ’Hierarchies of modal and temporal logics with reference pointers’, Journal of Logic, Language and Information, 5(1):1–24, 1996. · Zbl 0851.03003 · doi:10.1007/BF00215625
[22] Hemaspaandra, E., ’The price of universality’, Notre Dame Journal of Formal Logic, 37:174–203, 1996. · Zbl 0865.03032 · doi:10.1305/ndjfl/1040046086
[23] Hintikka, J., Knowledge and Belief, Cornell University Press, 1962. · Zbl 1384.03102
[24] Kanger, S., ’The morning star paradox’, Theoria, 1957, pp. 1–11. · Zbl 0081.01104
[25] Kanger, S., Provability in Logic, Almqvist & Wiksell, 1957. · Zbl 0077.01202
[26] Kripke, S., ’A completeness theorem in modal logic’, Journal of Symbolic Logic, 24:1–14, 1959. · Zbl 0091.00902 · doi:10.2307/2964568
[27] Kripke, S., ’Semantic analysis of modal logic I, normal propositional calculi’, Zeitschrift för mathemathische Logik und Grundlagen der Mathematik, 9:67–96, 1963. · Zbl 0118.01305 · doi:10.1002/malq.19630090502
[28] Kripke, S., ’Semantical considerations on modal logic’, Acta Philosophica Fennica, 16:83–94, 1963. · Zbl 0131.00602
[29] Lemmon, E., and D. Scott, The ’Lemmon Notes’: An Introduction to Modal Logic, Blackwell, 1977. · Zbl 0388.03006
[30] Lévy. A., A Hierarchy of Formulas in Set Theory, volume 57 of Memoirs ofthe American Mathematical Society, 1965. · Zbl 0202.30502
[31] Passy, S., and T. Tinchev, ’An essay in combinatory dynamic logic’, Information and computation, 93:263–332, 1991. · Zbl 0732.03021 · doi:10.1016/0890-5401(91)90026-X
[32] Prior, A., Past, Present and Future, Clarendon Press, Oxford, 1967. · Zbl 0169.29802
[33] Prior, A., Papers on Time and Tense, Oxford University Press, New edition, 2003. Edited by Hasle, Øhrstrom, Braöner, and Copeland.
[34] Sahlqvist, H., ’Completeness and correspondence in the first and second order semantics for modal logic’, in S. Kanger (ed.), Proceedings of the Third Scandinavian Logic Symposium, Uppsala 1973, North-Holland Publishing Company, 1975, pp. 110–143.
[35] Segerberg, K., An Essay in Classical Modal Logic, Filosofiska Studier 13, University of Uppsala, 1971. · Zbl 0311.02028
[36] ten Cate, B., Model Theory for Extended Modal Languages, PhD thesis, Institute for Logic, Language and Computation, University of Amsterdam, 2004.
[37] ten Cate, B., ’Interpolation for extended modal languages’, Journal of Symbolic Logic, 70(1):223–234, 2005. · Zbl 1089.03014 · doi:10.2178/jsl/1107298517
[38] ten Cate, B., ’Expressivity of second-order propositional modal logic’, Journal of Philosophical Logic, 35:209–223, 2006. · Zbl 1106.03016 · doi:10.1007/s10992-005-9012-9
[39] ten Cate, B., D. Gabelaia, and D. Sustretov, ’Modal languages for topology: expressivity and definability’, Manuscript. · Zbl 1172.03013
[40] ten Cate, B., and T. Litak, ’Topological perspective on the hybrid proof rules’, Electronic Notes in Theoretical Computer Science, To appear. International Workshop on Hybrid Logic 2006 (HyLo 2006).
[41] ten Cate, B., M. Marx, and P. Viana, ’Hybrid logics with Sahlqvist axioms’, Logic Journal of the IGPL, 13(3):293–300, 2005. · Zbl 1080.03006 · doi:10.1093/jigpal/jzi024
[42] Thomason, S., ’An incompleteness theorem in modal logic’, Theoria, 40:150–158, 1974. · Zbl 0287.02012
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.