A feasible theory of truth over combinatory algebra

Eberhard, Sebastian (2014). A feasible theory of truth over combinatory algebra. Annals of pure and applied logic, 165(5), pp. 1009-1033. Elsevier 10.1016/j.apal.2013.12.002

	Text 1-s2.0-S0168007213001772-main.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (386kB)
Preview	Text ebe14.pdf - Accepted Version Available under License Publisher holds Copyright. Download (450kB) | Preview

We define an applicative theory of truth TPT which proves totality exactly for the polynomial time computable functions. TPT has natural and simple axioms since nearly all its truth axioms are standard for truth theories over an applicative framework. The only exception is the axiom dealing with the word predicate. The truth predicate can only reflect elementhood in the words for terms that have smaller length than a given word. This makes it possible to achieve the very low proof-theoretic strength. Truth induction can be allowed without any constraints. For these reasons the system TPT has the high expressive power one expects from truth theories. It allows embeddings of feasible systems of explicit mathematics and bounded arithmetic. The proof that the theory TPT is feasible is not easy. It is not possible to apply a standard realisation approach. For this reason we develop a new realisation approach whose realisation functions work on directed acyclic graphs. In this way, we can express and manipulate realisation information more efficiently.

Interest & Impact

Downloads

161 since deposited on 26 Jan 2015
8 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item