On the complexity of arithmetical interpretations of modal formulae
The paper studies the complexity of formulas in the provability logic language \(L\) which have bounded arithmetical complexity (i.e. whose arithmetical interpretations are all \(\Delta^{\text{PA}}_ n\) for some fixed \(n\)). The main theorem of the paper is the following. Theorem. Suppose \(\phi\) is a formula of \(L\) such that for no Boolean combination \(\psi\) of boxed formulae \(\text{GL} \vdash \phi \leftrightarrow \psi\). Then for each \(n\) there exists an arithmetical interpretation \(f\) such that \(f(\phi)\in (\Delta^{\text{PA}}_ n- B^{\text{PA}}_ n)\). In particular, each modal formula which is not equivalent to any Boolean combination of boxed formulae admits arbitrarily complex arithmetical interpretations.
scientific article; zbMATH DE number 438619