Arithmetical realizations of modal formulas. Preliminary version.

Abstract

This thesis deals with provability logic. Strengthenings are obtained of some arithmetical completeness theorems by Berarducci, Carlson, Shavrukov, and Solovay. Conditions are provided for recursively enumerable sets of modal formulas to have natural counterparts in the form of recursively enumerable sets of arithmetical sentences. These conditions are all sufficient and some are also necessary. The modal formulas in question are expressed either in the language of bimodal provability logic or in the language of interpretability logic. The proofs of these results make particular use of a method involving Solovay functions that has been developed by Shavrukov and simplified by Zambella.Shavrukov has shown that the Magari algebras (i.e. the diagonalizable algebras) of two sufficiently sound and strong arithmetical theories are mutually embeddable. In this thesis it is shown that this result extends to Lindenbaum algebras that are equipped with two operators corresponding to the provability predicates of two different theories, one of which is much stronger than the other.A compactness theorem is obtained that pertains to the modal logic of interpretability over theories like Peano arithmetic and ZermeloFraenkel set theory. Finally certain simple phenomena of interpretability are investigated and in this connection a general solution to a problem of Orey from 1961 is provided.arithmetic, degrees of interpretability, diagonalizable algebra, interpretability logic, Magari algebra, metamathematics, modal logic, provability logic.