On the complexity of arithmetical interpretations of modal formulae
type: Item
instance of: scholarly article
title: On the complexity of arithmetical interpretations of modal formulae
zbMATH Open document ID: 0802.03011
DOI: 10.1007/BF01375554
author: Lev D. Beklemishev
published in: Archive for Mathematical Logic
publication date: 1994-12-12T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03B45
Mathematics Subject Classification ID: 03F40
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 438619
zbMATH Keywords: modal logic
zbMATH Keywords: provability interpretation
zbMATH Keywords: complexity of formulas
zbMATH Keywords: provability logic
zbMATH Keywords: bounded arithmetical complexity
zbMATH Keywords: arithmetical interpretations
reviewed by: Vladimir Rybakov
MaRDI profile type: Publication
cites work: The relation of A to Prov ˹A˺ in the Lindenbaum sentence algebra
cites work: Sentences implying their own provability
cites work: Self-reference and modal logic
cites work: Reflection Principles and their Use for Establishing the Complexity of Axiomatic Systems
cites work: Provability interpretations of modal logic
full work available at URL: https://doi.org/10.1007/bf01375554
OpenAlex ID: W2034796493
description: scientific article; zbMATH DE number 438619