Supremum in the Lattice of Interpretability
Paula Henk
Abstract:
This thesis is located in the field of provability and
interpretability logic, where modal logic is used in the study of
formal systems of arithmetic. The central notion of this thesis is
that of interpretability. The notion of interpretability can be seen
as a tool for comparing axiomatic theories. Intuitively, if a theory T
interprets a theory S , T is at least as strong as S. The modal logic
ILM captures exactly what Peano Arithemtic (PA) can prove about
interpretability between nite extensions of itself. As it turns out,
nite extensions of PA form a lattice under the relation of
interpretability, i.e. any two theories have an inmum and a supremum
in the interpretability ordering. The supremum in this lattice is the
main subject of study in this thesis.
We will extend the logic ILM with a binary operator for the supremum,
and explore the possibilities of having a modal semantics for the
resulting system ILMS. For that purpose, the supremum will be studied
both from the arithmetical as well as from the modal
perspective. First, we will see that the exact content of the logic
ILMS depends on the formula that is chosen as the arithmetical
representative of the supremum. This is dierent from ILM, where the
meaning of the modal symbols is xed from the outset. Proceeding to the
modal side, we establish an important negative result: there can be no
structural characterization of ILM{models that validate the dening
axiom for the supremum. This precludes the possibility of having a
relational semantics for the system ILMS | at least one that would
extend the usual semantics for ILM. Finally, we examine an elegant but
unfortunately failed attempt to nd a relational semantics for a
particular representative of the supremum.