Truth and feasible reducibility

Journal of Symbolic Logic 85 (1):367-421 (2020)
  Copy   BIBTEX

Abstract

Let ${\cal T}$ be any of the three canonical truth theories CT^− (compositional truth without extra induction), FS^− (Friedman–Sheard truth without extra induction), or KF^− (Kripke–Feferman truth without extra induction), where the base theory of ${\cal T}$ is PA. We establish the following theorem, which implies that ${\cal T}$ has no more than polynomial speed-up over PA. Theorem.${\cal T}$is feasibly reducible to PA, in the sense that there is a polynomial time computable function f such that for every ${\cal T}$-proof π of an arithmetical sentence ϕ, f(π) is a PA-proof of ϕ.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,296

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

Disquotational truth and analyticity.Volker Halbach - 2001 - Journal of Symbolic Logic 66 (4):1959-1973.
Disquotational Truth and Analyticity.Volker Halbach - 2001 - Journal of Symbolic Logic 66 (4):1959-1973.
Semilattices and the Ramsey property.Miodrag Sokić - 2015 - Journal of Symbolic Logic 80 (4):1236-1259.

Analytics

Added to PP
2019-09-21

Downloads
29 (#569,467)

6 months
7 (#491,177)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Citations of this work

Incompleteness Via Paradox and Completeness.Walter Dean - 2020 - Review of Symbolic Logic 13 (3):541-592.
Comparing Axiomatic Theories of Truth.Mateusz Łełyk - 2019 - Studia Semiotyczne 33 (2):255-286.

View all 7 citations / Add more citations

References found in this work

No references found.

Add more references