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

[img] Text
1-s2.0-S0168007213001772-main.pdf - Published Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (386kB) | Request a copy
[img]
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.

Item Type: Journal Article (Original Article)
Division/Institute: 08 Faculty of Science > Institute of Computer Science (INF) > Logic and Theory Group (LTG)
08 Faculty of Science > Institute of Computer Science (INF)
UniBE Contributor: Eberhard, Sebastian
Subjects: 000 Computer science, knowledge & systems
500 Science > 510 Mathematics
ISSN: 0168-0072
Publisher: Elsevier
Language: English
Submitter: Florian Ranzi
Date Deposited: 26 Jan 2015 08:49
Last Modified: 21 Sep 2015 09:49
Publisher DOI: 10.1016/j.apal.2013.12.002
BORIS DOI: 10.7892/boris.61791
URI: http://boris.unibe.ch/id/eprint/61791

Actions (login required)

Edit item Edit item
Provide Feedback