Skip to main content
SpringerLink
Log in

Pure Extensions, Proof Rules, and Hybrid Axiomatics

  • Published:
Studia Logica Aims and scope Submit manuscript

Abstract

In this paper we argue that hybrid logic is the deductive setting most natural for Kripke semantics. We do so by investigating hybrid axiomatics for a variety of systems, ranging from the basic hybrid language (a decidable system with the same complexity as orthodox propositional modal logic) to the strong Priorean language (which offers full first-order expressivity).

We show that hybrid logic offers a genuinely first-order perspective on Kripke semantics: it is possible to define base logics which extend automatically to a wide variety of frame classes and to prove completeness using the Henkin method. In the weaker languages, this requires the use of non-orthodox rules. We discuss these rules in detail and prove non-eliminability and eliminability results. We also show how another type of rule, which reflects the structure of the strong Priorean language, can be employed to give an even wider coverage of frame classes. We show that this deductive apparatus gets progressively simpler as we work our way up the expressivity hierarchy, and conclude the paper by showing that the approach transfers to first-order hybrid logic.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Areces, C., P. Blackburn, and M. Marx, ‘Hybrid logics: Characterization, interpolation and complexity’, Journal of Symbolic Logic, 66(3):977–1010, 2001.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  5. Blackburn, P., ‘Internalizing labelled deduction’, Journal of Logic and Computation, 10:137–168, 2000.

    Article  Google Scholar 

  6. Blackburn, P., ‘Arthur Prior and hybrid logic’, Synthese, 150:329–372, 2006.

    Article  Google Scholar 

  7. Blackburn, P., M. de Rijke, and Y. Venema, Modal logic, Cambridge University Press, Cambridge, UK, 2001.

    Google Scholar 

  8. Blackburn, P., and M. Marx, ‘Constructive interpolation in hybrid logic’, Journal of Symbolic Logic, 68(2):463–480, 2003.

    Article  Google Scholar 

  9. Blackburn, P., and J. ‘Seligman, Hybrid languages’, Journal of Logic, Language and Information, 4:251–272, 1995.

    Article  Google Scholar 

  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.

  12. Blackburn, P., and M. Tzakova, ‘Hybrid languages and temporal logic’, Logic Journal of the IGPL, 7(1):27–54, 1999.

    Article  Google Scholar 

  13. Braöner, T.. ‘Natural deduction for hybrid logic’, Journal of Logic and Computation, 14(3):329–353, 2004.

    Article  Google Scholar 

  14. Bull, R., ‘An approach to tense logic’, Theoria, 36:282–300, 1970.

    Article  Google Scholar 

  15. Buss, S., ‘Bounded arithmetic and propositional proof complexity’, in H. Schwichtenberg (ed.), Logic and Computation, Springer, 1997, pp. 67–122.

  16. de Rijke, M., ‘The modal logic of inequality’, Journal of Symbolic Logic, 57(2):566–584, 1992.

    Article  Google Scholar 

  17. Feferman, S., ‘Persistent and invariant formulas for outer extensions’, Compositio Mathematica, 20:29–52, 1968.

    Google Scholar 

  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.

    Article  Google Scholar 

  19. Fine, K., ‘An incomplete logic containing S4’, Theoria, 40:23–29, 1974.

    Article  Google Scholar 

  20. Gargov, G., and V. Goranko, ‘Modal logic with names’, Journal of Philosophical Logic, 22:607–636, 1993.

    Article  Google Scholar 

  21. Goranko, V., ‘Hierarchies of modal and temporal logics with reference pointers’, Journal of Logic, Language and Information, 5(1):1–24, 1996.

    Article  Google Scholar 

  22. Hemaspaandra, E., ‘The price of universality’, Notre Dame Journal of Formal Logic, 37:174–203, 1996.

    Article  Google Scholar 

  23. Hintikka, J., Knowledge and Belief, Cornell University Press, 1962.

  24. Kanger, S., ‘The morning star paradox’, Theoria, 1957, pp. 1–11.

  25. Kanger, S., Provability in Logic, Almqvist & Wiksell, 1957.

  26. Kripke, S., ‘A completeness theorem in modal logic’, Journal of Symbolic Logic, 24:1–14, 1959.

    Article  Google Scholar 

  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.

    Google Scholar 

  28. Kripke, S., ‘Semantical considerations on modal logic’, Acta Philosophica Fennica, 16:83–94, 1963.

    Google Scholar 

  29. Lemmon, E., and D. Scott, The ‘Lemmon Notes’: An Introduction to Modal Logic, Blackwell, 1977.

  30. Lévy. A., A Hierarchy of Formulas in Set Theory, volume 57 of Memoirs ofthe American Mathematical Society, 1965.

  31. Passy, S., and T. Tinchev, ‘An essay in combinatory dynamic logic’, Information and computation, 93:263–332, 1991.

    Article  Google Scholar 

  32. Prior, A., Past, Present and Future, Clarendon Press, Oxford, 1967.

    Google Scholar 

  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.

  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.

    Article  Google Scholar 

  38. ten Cate, B., ‘Expressivity of second-order propositional modal logic’, Journal of Philosophical Logic, 35:209–223, 2006.

    Article  Google Scholar 

  39. ten Cate, B., D. Gabelaia, and D. Sustretov, ‘Modal languages for topology: expressivity and definability’, Manuscript.

  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.

    Article  Google Scholar 

  42. Thomason, S., ‘An incompleteness theorem in modal logic’, Theoria, 40:150–158, 1974.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. INRIA Lorraine, 615 rue du Jardin Botanique, 54602, Villers les Nancy Cedex, France

    P. Blackburn

  2. ISLA, Informatics Institute, Universiteit van Amsterdam , Kruislaan 403, 1098, SJ Amsterdam, The Netherlands

    B. ten Cate

Authors
  1. P. Blackburn
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B. ten Cate
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to P. Blackburn.

Additional information

A preliminary version of this paper was presented at the fifth conference on Advances in Modal Logic (AiML 2004) in Manchester. We would like to thank Maarten Marx for his comments on an early draft and Agnieszka Kisielewska for help with the proof reading.

Special Issue Ways of Worlds II. On Possible Worlds and Related Notions Edited by Vincent F. Hendricks and Stig Andur Pedersen

Rights and permissions

Reprints and permissions

About this article

Cite this article

Blackburn, P., Cate, B.t. Pure Extensions, Proof Rules, and Hybrid Axiomatics. Stud Logica 84, 277–322 (2006). https://doi.org/10.1007/s11225-006-9009-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11225-006-9009-6

Keywords

Search

Navigation