T3 - MULTI-DIMENSIONAL MODAL LOGIC
Horario: 14 a 17 hs.
PROFESOR: Dr. Maarten Marx.
El profesor Maarten Marx fue estudiante de doctorado de la Universidad de Amsterdam y del Instituto de Matemática de la Academia de Ciencias Húngara. Obtuvo el título en 1995. Es Investigador Asociado del Departamento de Computación del Imperial College de Londres, Inglaterra. Es coautor de un libro sobre Multi-dimensional modal logic.
PROGRAMA:
Kripke style Modal Logic K,T,S4,S5, etc. Correspondence theory. Sahlqvist theory. Standard translation and bisimulation theorem. Expressive power of S5 equals that of monadic predicate logic.
More expressive power: the difference operator D. Expressibility: first order fragment it captures. Axiomatics, disjoint unions, zigzagmorphims. Decidability, filtration, mosaic method.
Interpolation, failure of it with D. Multimodal logics with D, i.e. temporal logic. Irreflexivity rule.
Expressibility. How to go beyond the “one-free-variable fragment”: true multi-dimensional modal logic. We look at First Order logic as a modal logic, highlight difficult points, give an overview of results and introduce our terminology.
We give a completeness theorem for first-order logic with two variables, introducing the powerful step-by-step method. (Time permitting we will also look at arrow logic, the modal counterpart of relation algebras.)
Decidability and Complexity. We prove decidability of first order logic with two variables, and the generalized "locally cubic" first order logic. We show their complexity and we give very general proof-techniques.
Axiomatics. We show how to use Gabbay's irreflexivity rule to overcome non-finite axiomatizability results. We start with a simple example concerning two-dimensional temporal logic (the temporal logic of intervals) and then prove a completeness theorem for either arrow logic or the modal counterpart of first-order logic.
Interpolation. Relevance of interpolation from a computational view. When do we have it? When do we loose it? Concrete examples.
PREREQUISITOS:
Conocimientos de Lógica de Primer Orden.
El curso se dictará en inglés.
Volver a ECI 1996