
Modal logics between propositional and firstorder
Prof Melvin Fitting
Department of Mathematics and Computer Science,
Lehman College,
New York.
Abstract
One can add the machinery of relation symbols and terms to a
propositional modal logic without adding quantifiers. Ordinarily this
is no extension beyond the propositional. But if terms are allowed to
be nonrigid, a scoping mechanism (usually written using lambda
abstraction) must also be introduced to avoid ambiguity. Since
quantifiers are not present, this is not really a firstorder logic,
but it is not exactly propositional either. I will show that for
propositional logics such as K, T and D, adding such machinery
produces a decidable logic, but adding it to logics between K4 and S5
produces an undecidable one. (Transitivity is the villain here.) The
proof of undecidability consists of showing that classical firstorder
logic can be embedded.
Place: Information technology, Uppsala University
Room: 1510
Time: 10.30
Room 1510 is in Building 1, Floor 5, room 10
(in the southern part of the building).
Help on how to find ASTEC seminars.
Updated 08Jan2001 15:16 by Roland Grönroos
email: info at astec.uu.se
Location: http://www.astec.uu.se/Seminars/sem010111.shtml
