Switch to: References

Add citations

You must login to add citations.
  1. Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones. [REVIEW]Andreas Weiermann - 1995 - Archive for Mathematical Logic 34 (5):313-330.
    Let T(Ω) be the ordinal notation system from Buchholz-Schütte (1988). [The order type of the countable segmentT(Ω)0 is — by Rathjen (1988) — the proof-theoretic ordinal the proof-theoretic ordinal ofACA 0 + (Π 1 l −TR).] In particular let ↦Ω a denote the enumeration function of the infinite cardinals and leta ↦ ψ0 a denote the partial collapsing operation on T(Ω) which maps ordinals of T(Ω) into the countable segment TΩ 0 of T(Ω). Assume that the (fast growing) extended Grzegorczyk (...)
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • The Ackermann functions are not optimal, but by how much?H. Simmons - 2010 - Journal of Symbolic Logic 75 (1):289-313.
    By taking a closer look at the construction of an Ackermann function we see that between any primitive recursive degree and its Ackermann modification there is a dense chain of primitive recursive degrees.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy.S. S. Wainer - 1972 - Journal of Symbolic Logic 37 (2):281-292.
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • The intrinsic difficulty of recursive functions.F. W. Kroon - 1996 - Studia Logica 56 (3):427 - 454.
    This paper deals with a philosophical question that arises within the theory of computational complexity: how to understand the notion of INTRINSIC complexity or difficulty, as opposed to notions of difficulty that depend on the particular computational model used. The paper uses ideas from Blum's abstract approach to complexity theory to develop an extensional approach to this question. Among other things, it shows how such an approach gives detailed confirmation of the view that subrecursive hierarchies tend to rank functions in (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Dickson’s lemma and weak Ramsey theory.Yasuhiko Omata & Florian Pelupessy - 2019 - Archive for Mathematical Logic 58 (3-4):413-425.
    We explore the connections between Dickson’s lemma and weak Ramsey theory. We show that a weak version of the Paris–Harrington principle for pairs in c colors and miniaturized Dickson’s lemma for c-tuples are equivalent over \. Furthermore, we look at a cascade of consequences for several variants of weak Ramsey’s theorem.
    Download  
     
    Export citation  
     
    Bookmark  
  • Proof theory and ordinal analysis.W. Pohlers - 1991 - Archive for Mathematical Logic 30 (5-6):311-376.
    In the first part we show why ordinals and ordinal notations are naturally connected with proof theoretical research. We introduce the program of ordinal analysis. The second part gives examples of applications of ordinal analysis.
    Download  
     
    Export citation  
     
    Bookmark   20 citations  
  • Subsystems of true arithmetic and hierarchies of functions.Z. Ratajczyk - 1993 - Annals of Pure and Applied Logic 64 (2):95-152.
    Ratajczyk, Z., Subsystems of true arithmetic and hierarchies of functions, Annals of Pure and Applied Logic 64 95–152. The combinatorial method coming from the study of combinatorial sentences independent of PA is developed. Basing on this method we present the detailed analysis of provably recursive functions associated with higher levels of transfinite induction, I, and analyze combinatorial sentences independent of I. Our treatment of combinatorial sentences differs from the one given by McAloon [18] and gives more natural sentences. The same (...)
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • Reverse mathematical bounds for the Termination Theorem.Silvia Steila & Keita Yokoyama - 2016 - Annals of Pure and Applied Logic 167 (12):1213-1241.
    Download  
     
    Export citation  
     
    Bookmark   1 citation