On Logics and Semantics for Interpretability

Abstract

We study various properties of formalised relativised interpretability. In the central part of this thesis we study for different interpretability logics the following aspects: completeness for modal semantics, decidability and algorithmic complexity.

In particular, we study two basic types of relational semantics for interpretability logics. One is the Veltman semantics, which we shall refer to as the regular or ordinary semantics; the other is called generalised Veltman semantics. In the recent years and especially during the writing of this thesis, generalised Veltman semantics was shown to be particularly well-suited as a relational semantics for interpretability logics. In particular, modal completeness results are easier to obtain in some cases; and decidability can be proven via filtration in all known cases. We prove various new and reprove some old completeness results with respect to the generalised semantics. We use the method of filtration to obtain the finite model property for various logics.

Apart from results concerning semantics in its own right, we also apply methods from semantics to determine decidability (implied by the finite model property) and complexity of provability (and consistency) problems for certain interpretability logics.

From the arithmetical standpoint, we explore three different series of interpretability principles. For two of them, for which arithmetical and modal soundness was already known, we give a new proof of arithmetical soundness. The third series results from our modal considerations. We prove it arithmetically sound and also characterise frame conditions w.r.t. ordinary Veltman semantics. We also prove results concerning the new series and generalised Veltman semantics.

Abstract prepared by Luka Mikec.

E-mail: [email protected]

URL: http://hdl.handle.net/2445/177373