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

Ali Enayat
University of Gothenburg
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 ϕ.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1017/jsl.2019.24
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 50,391
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Comparing Axiomatic Theories of Truth.Mateusz Łełyk - 2019 - Studia Semiotyczne 33 (2):255-286.

Add more citations

Similar books and articles

Models of Positive Truth.Mateusz Łełyk & Bartosz Wcisło - 2019 - Review of Symbolic Logic 12 (1):144-172.
Models of Weak Theories of Truth.Mateusz Łełyk & Bartosz Wcisło - 2017 - Archive for Mathematical Logic 56 (5-6):453-474.
Strong Enumeration Reducibilities.Roland Sh Omanadze & Andrea Sorbi - 2006 - Archive for Mathematical Logic 45 (7):869-912.
A New Reducibility Between Turing‐ and Wtt‐Reducibility.Sui Yuefei - 1994 - Mathematical Logic Quarterly 40 (1):106-110.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
A C.E. Real That Cannot Be SW-Computed by Any Ω Number.George Barmpalias & Andrew E. M. Lewis - 2006 - Notre Dame Journal of Formal Logic 47 (2):197-209.
Embeddings in the Strong Reducibilities Between 1 and Npm.Phil Watson - 1997 - Mathematical Logic Quarterly 43 (4):559-568.
Bounds in the Turing Reducibility of Functions.Karol Habart & K. Habart - 1992 - Mathematical Logic Quarterly 38 (1):423-430.
A Feasible Theory of Truth Over Combinatory Algebra.Sebastian Eberhard - 2014 - Annals of Pure and Applied Logic 165 (5):1009-1033.
Bounded Enumeration Reducibility and its Degree Structure.Daniele Marsibilio & Andrea Sorbi - 2012 - Archive for Mathematical Logic 51 (1-2):163-186.
Supervenience and Reducibility: An Odd Couple.Ausonio Marras - 1994 - Philosophical Quarterly 44 (171):215-222.


Added to PP index

Total views
10 ( #800,178 of 2,326,144 )

Recent downloads (6 months)
5 ( #164,573 of 2,326,144 )

How can I increase my downloads?


My notes