dc.creator | Cordón Franco, Andrés | es |
dc.creator | Lara Martín, Francisco Félix | es |
dc.date.accessioned | 2019-06-24T08:34:25Z | |
dc.date.available | 2019-06-24T08:34:25Z | |
dc.date.issued | 2014 | |
dc.identifier.citation | Cordón Franco, A. y Lara Martín, F.F. (2014). Local induction and provably total computable functions. Annals of Pure and Applied Logic, 165 (9), 1429-1444. | |
dc.identifier.issn | 0168-0072 | es |
dc.identifier.uri | https://hdl.handle.net/11441/87547 | |
dc.description.abstract | Let I¦−
2 denote the fragment of Peano Arithmetic obtained by restricting the
induction scheme to parameter free ¦2 formulas. Answering a question of R.
Kaye, L. Beklemishev showed that the provably total computable functions
of I¦−
2 are, precisely, the primitive recursive ones. In this work we give a new
proof of this fact through an analysis of certain local variants of induction
principles closely related to I¦−
2 . In this way, we obtain a more direct answer
to Kaye’s question, avoiding the metamathematical machinery (reflection
principles, provability logic,...) needed for Beklemishev’s original proof.
Our methods are model–theoretic and allow for a general study of I¦−
n+1
for all n ¸ 0. In particular, we derive a new conservation result for these
theories, namely that I¦−
n+1 is ¦n+2–conservative over I§n for each n ¸ 1. | es |
dc.description.sponsorship | Ministerio de Ciencia e Innovación MTM2008–06435 | es |
dc.description.sponsorship | Ministerio de Ciencia e Innovación MTM2011–26840 | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Elsevier | es |
dc.relation.ispartof | Annals of Pure and Applied Logic, 165 (9), 1429-1444. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | First order arithmetic | es |
dc.subject | Conservation results | es |
dc.subject | Parameter free induction | es |
dc.subject | Primitive recursive functions | es |
dc.title | Local induction and provably total computable functions | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial | es |
dc.relation.projectID | MTM2008–06435 | es |
dc.relation.projectID | MTM2011–26840 | es |
dc.relation.publisherversion | https://www.sciencedirect.com/science/article/pii/S0168007214000438 | es |
dc.identifier.doi | 10.1016/j.apal.2014.04.012 | es |
idus.format.extent | 23 | es |
dc.journaltitle | Annals of Pure and Applied Logic | es |
dc.publication.volumen | 165 | es |
dc.publication.issue | 9 | es |
dc.publication.initialPage | 1429 | es |
dc.publication.endPage | 1444 | es |