On the complexity of arithmetical interpretations of modal formulae (Q688859): Difference between revisions

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.