Notre Dame Journal of Formal Logic 53 (2):133-154 (2012)

Authors
Thomas Icard
Stanford University
Abstract
The provability logic of a theory $T$ is the set of modal formulas, which under any arithmetical realization are provable in $T$. We slightly modify this notion by requiring the arithmetical realizations to come from a specified set $\Gamma$. We make an analogous modification for interpretability logics. We first study provability logics with restricted realizations and show that for various natural candidates of $T$ and restriction set $\Gamma$, the result is the logic of linear frames. However, for the theory Primitive Recursive Arithmetic (PRA), we define a fragment that gives rise to a more interesting provability logic by capitalizing on the well-studied relationship between PRA and I$\Sigma_1$. We then study interpretability logics, obtaining upper bounds for IL(PRA), whose characterization remains a major open question in interpretability logic. Again this upper bound is closely related to linear frames. The technique is also applied to yield the nontrivial result that IL(PRA) $\subset$ ILM
Keywords provability logic   interpretability logic   restricted substitutions   GLP   ISigma1   PRA
Categories (categorize this paper)
DOI 10.1215/00294527-1715653
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,379
Through your library

References found in this work BETA

Solution of a Problem of Leon Henkin.M. H. Löb - 1955 - Journal of Symbolic Logic 20 (2):115-118.
The Interpretability Logic of Peano Arithmetic.Alessandro Berarducci - 1990 - Journal of Symbolic Logic 55 (3):1059-1089.

View all 23 references / Add more references

Citations of this work BETA

The Polytopologies of Transfinite Provability Logic.David Fernández-Duque - 2014 - Archive for Mathematical Logic 53 (3-4):385-431.

Add more citations

Similar books and articles

Bimodal Logics for Extensions of Arithmetical Theories.Lev D. Beklemishev - 1996 - Journal of Symbolic Logic 61 (1):91-124.
Interpretability Over Peano Arithmetic.Claes Strannegård - 1999 - Journal of Symbolic Logic 64 (4):1407-1425.
The Interpretability Logic of Peano Arithmetic.Alessandro Berarducci - 1990 - Journal of Symbolic Logic 55 (3):1059-1089.
Explicit Provability and Constructive Semantics.Sergei N. Artemov - 2001 - Bulletin of Symbolic Logic 7 (1):1-36.

Analytics

Added to PP index
2012-05-10

Total views
36 ( #318,207 of 2,519,679 )

Recent downloads (6 months)
1 ( #406,314 of 2,519,679 )

How can I increase my downloads?

Downloads

My notes