The Logic of Exact Covers: Completeness and Uniform Interpolation
Dirk Pattinson (ANU)
LOGIC AND COMPUTATION SEMINARDATE: 2013-06-11
TIME: 14:00:00 - 15:00:00
LOCATION: RSISE Seminar Room, ground floor, building 115, cnr. North and Daley Roads, ANU
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
We show that all (not necessarily normal or monotone) modal logics that can be axiomatised in rank-1 have the interpolation property, and that in fact interpolation is uniform if the logics just have finitely many modal operators. As immediate applications, we obtain previously unknown interpolation theorems for a range of modal logics, containing probabilistic and graded modal logic, alternating temporal logic and some variants of conditional logic.
Technically, this is achieved by translating to and from a new (coalgebraic) logic introduced in this paper, the emph{logic of exact covers}. It is interpreted over coalgebras for an endofunctor on the category of sets that also directly determines the syntax. Apart from closure under bisimulation quantifiers (and hence interpolation), we also provide a complete tableaux calculus and establish both the Hennessy-Milner and the small model property for this logic.
