Hostname: page-component-7c8c6479df-fqc5m Total loading time: 0 Render date: 2024-03-28T12:53:34.885Z Has data issue: false hasContentIssue false

ON DEFINABILITY IN MULTIMODAL LOGIC

Published online by Cambridge University Press:  05 October 2009

JOSEPH Y. HALPERN*
Affiliation:
Computer Science Department, Cornell University
DOV SAMET*
Affiliation:
The Faculty of Management, Tel Aviv University
ELLA SEGEV*
Affiliation:
Faculty of Industrial Engineering and Management, Technion—Israel Institute of Technology
*
*COMPUTER SCIENCE DEPARTMENT, CORNELL UNIVERSITY, ITHACA, NY 14853 E-mail:halpern@cs.cornell.edu
THE FACULTY OF MANAGEMENT, TEL AVIV UNIVERSITY, TEL AVIV, 69978, ISRAEL E-mail:samet@post.tau.ac.il
FACULTY OF INDUSTRIAL ENGINEERING AND MANAGEMENT, TECHNION—ISRAEL INSTITUTE OF TECHNOLOGY, ISRAEL E-mail:esegev@ie.technion.ac.il

Abstract

Three notions of definability in multimodal logic are considered. Two are analogous to the notions of explicit definability and implicit definability introduced by Beth in the context of first-order logic. However, while by Beth’s theorem the two types of definability are equivalent for first-order logic, such an equivalence does not hold for multimodal logics. A third notion of definability, reducibility, is introduced; it is shown that in multimodal logics, explicit definability is equivalent to the combination of implicit definability and reducibility. The three notions of definability are characterized semantically using (modal) algebras. The use of algebras, rather than frames, is shown to be necessary for these characterizations.

Type
Research Article
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

BIBLIOGRAPHY

Andréka, H., van Benthem, J., & Németi, I. (1998). Modal languages and bounded fragments of predicate logic. Journal of Philosophical Logic, 27(3), 217274.CrossRefGoogle Scholar
Beth, E. W. (1953). On Padoa’s method in the theory of definition. Indagationes Mathematicae, 15, 330339.CrossRefGoogle Scholar
Blackburn, P., de Rijke, M., & Venema, Y. (2001). Modal Logic. Cambridge Tracts in Theoretical Computer Science, Vol. 53. Cambridge, UK: Cambridge University Press.CrossRefGoogle Scholar
Halpern, J. Y., Samet, D., & Segev, E. (2008). Defining knowledge in terms of belief: the modal logic perspective. Review of Symbolic Logic, forthcoming. Available from: http://www.cs.cornell.edu/home/halpern/papers.Google Scholar
van der Hoek, W. (1993). Systems for knowledge and belief. Journal of Logic and Computation, 3(2), 173195.CrossRefGoogle Scholar
Jónsson, B., & Tarski, A. (1951). Boolean algebras with operators, Part I. American Journal of Mathematics, 73, 891939.CrossRefGoogle Scholar
Jónsson, B., & Tarski, A. (1952). Boolean algebras with operators, Part II. American Journal of Mathematics, 74, 127162.CrossRefGoogle Scholar
Kracht, M. (1999). Tools and Techniques in Modal Logic. Studies in Logic and the Foundations of Mathematics, Vol. 142. Amsterdam, The Netherlands: Elsevier.CrossRefGoogle Scholar
Lenzen, W. (1979). Epistemoligische betrachtungen zu [S4, S5]. Erkenntnis, 14, 3356.CrossRefGoogle Scholar
Maksimova, L. L. (1992a). An analogue of Beth’s theorem in normal extensions of the model logic K4. Siberian Mathematical Journal, 33(6), 10521065.CrossRefGoogle Scholar
Maksimova, L. L. (1992b). Modal logics and varieties of modal algebras: The Beth properties, interpolation, and amalgamation. Algebra and Logic, 31(2), 90105.CrossRefGoogle Scholar
Pelletier, F. J., & Urquhart, A. (2003). Synonymous logics. Journal of Philosophical Logic, 32(3), 259285.CrossRefGoogle Scholar