Truth and feasible reducibility

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


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 ϕ.



    Upload a copy of this work     Papers currently archived: 91,088

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

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

25 (#560,650)

6 months
4 (#404,301)

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