Complexity of the interpretability logics ILW and ILP

Logic Journal of the IGPL 31 (1):194-213 (2023)
  Copy   BIBTEX

Abstract

The interpretability logic ILP is the interpretability logic of all sufficiently strong |$\varSigma _1$|-sound finitely axiomatised theories, such as the Gödel-Bernays set theory. The interpretability logic IL is a strict subset of the intersection of the interpretability logics of all so-called reasonable theories, IL(All). It is known that both ILP and ILW are decidable, however their complexity has not been resolved previously. In [10] it was shown that the basic interpretability logic IL is PSPACE-complete. Here we prove the same for ILP and ILW.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,261

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Interpretability over peano arithmetic.Claes Strannegård - 1999 - Journal of Symbolic Logic 64 (4):1407-1425.
Modal Matters for Interpretability Logics.Evan Goris & Joost Joosten - 2008 - Logic Journal of the IGPL 16 (4):371-412.
Interpretability over peano arithmetic.Claes Strannegård - 1999 - Journal of Symbolic Logic 64 (4):1407-1425.
Interpretability over peano arithmetic.Claes Strannegård - 1999 - Journal of Symbolic Logic 64 (4):1407-1425.
Interpolation and the Interpretability Logic of PA.Evan Goris - 2006 - Notre Dame Journal of Formal Logic 47 (2):179-195.
The formalization of interpretability.Albert Visser - 1991 - Studia Logica 50 (1):81 - 105.

Analytics

Added to PP
2022-04-09

Downloads
9 (#1,258,729)

6 months
1 (#1,478,781)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations