Skip Navigation



Journal of Logic and Computation Advance Access published online on November 8, 2007
Journal of Logic and Computation, doi:10.1093/logcom/exm035
This Article
Right arrow Full Text
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
17/6/1083    most recent
exm035v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by den Boer, A.
Right arrow Articles by Weiermann, A.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2007. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original papers

A Sharp Phase Transition Threshold for Elementary Descent Recursive Functions

Arnoud den Boer

Fakulteit Bètawetenschappen, Departement Wiskunde, PO Box 80010, 3508 TA Utrecht, The Netherlands. E-mail: avdenboer{at}gmail.com

Andreas Weiermann

Vakgroep Zuivere Wiskunde en Computeralgebra, Ghent University, Krijgslaan 281 - Gebouw S22, B9000 Gent, Belgium. E-mail: weierman{at}cage.ugent.be

Received 19 October 2006.


  Abstract

Harvey Friedman introduced natural independence results for the Peano axioms (PA) via certain schemes of combinatorial well-foundedness. We consider in this article parameterized versions of a specific Friedman-style scheme and classify exactly the threshold for the transition from provability to unprovability in PA. For this purpose we fix a natural Schütte-style bijection between the ordinals below {varepsilon}0 and the positive integers. This coding induces a natural well ordering {precedes} on the positive integers. Using bounds on the asymptotic of the resulting global count functions we classify precisely the phase transition for the parameterized hierarchy of elementary descent recursive functions and hence for the combinatorial well-foundedness scheme. Let CWF(g) be the assertion that for all natural numbers K there exists a natural number M which is so large that there does not exist a strictly {precedes}-descending sequence m0,...,mM of positive integers such that for every i with 0 ≤ i ≤ M we have that mi ≤ K + g(i). For classifying the provable from the unprovable version of CWF(g) (as a problem depending on g) let Formula where | · |k denotes the k-times iterated binary length function and where Formula denotes the functional inverse of the {alpha}-th function from the fast growing hierarchy. Then our main result is: PA proves CWF (f{alpha}) iff {alpha} < {varepsilon}0.

Keywords: Proof theory; phase transition; elementary descent recursive functions; multiplicative number theory.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.