The Review of Symbolic Logic

Research Article

ON DEFINABILITY IN MULTIMODAL LOGIC

JOSEPH Y. HALPERNa1 c1, DOV SAMETa2 c2 and ELLA SEGEVa3 c3

a1 Computer Science Department, Cornell University

a2 The Faculty of Management, Tel Aviv University

a3 Faculty of Industrial Engineering and Management, Technion—Israel Institute of Technology

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.

(Received January 06 2008)

Correspondence:

c1 COMPUTER SCIENCE DEPARTMENT, CORNELL UNIVERSITY, ITHACA, NY 14853 E-mail: halpern@cs.cornell.edu

c2 THE FACULTY OF MANAGEMENT, TEL AVIV UNIVERSITY, TEL AVIV, 69978, ISRAEL E-mail: samet@post.tau.ac.il

c3 FACULTY OF INDUSTRIAL ENGINEERING AND MANAGEMENT, TECHNION—ISRAEL INSTITUTE OF TECHNOLOGY, ISRAEL E-mail: esegev@ie.technion.ac.il