41 found
Sort by:
  1. Andrey Bovykin & Andreas Weiermann (forthcoming). The Strength of Infinitary Ramseyan Principles Can Be Accessed by Their Densities. Annals of Pure and Applied Logic.
    Direct download  
     
    My bibliography  
     
    Export citation  
  2. Sy-David Friedman, Michael Rathjen & Andreas Weiermann (2013). Slow Consistency. Annals of Pure and Applied Logic 164 (3):382-393.
    The fact that “natural” theories, i.e. theories which have something like an “idea” to them, are almost always linearly ordered with regard to logical strength has been called one of the great mysteries of the foundation of mathematics. However, one easily establishes the existence of theories with incomparable logical strengths using self-reference . As a result, PA+Con is not the least theory whose strength is greater than that of PA. But still we can ask: is there a sense in which (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Andreas Weiermann & Gunnar Wilken (2013). Goodstein Sequences for Prominent Ordinals Up to the Ordinal Of. Annals of Pure and Applied Logic 164 (12):1493-1506.
    We introduce strong Goodstein principles which are true but unprovable in strong impredicative theories like IDn.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  4. Michiel De Smet & Andreas Weiermann (2012). Goodstein Sequences for Prominent Ordinals Up to the Bachmann–Howard Ordinal. Annals of Pure and Applied Logic 163 (6):669-680.
  5. Lev Gordeev & Andreas Weiermann (2012). Phase Transitions of Iterated Higman-Style Well-Partial-Orderings. Archive for Mathematical Logic 51 (1-2):127-161.
    We elaborate Weiermann-style phase transitions for well-partial-orderings (wpo) determined by iterated finite sequences under Higman-Friedman style embedding with Gordeev’s symmetric gap condition. For every d-times iterated wpo ${\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d}\right)}$ in question, d > 1, we fix a natural extension of Peano Arithmetic, ${T \supseteq \sf{PA}}$ , that proves the corresponding second-order sentence ${\sf{WPO}\left({\rm S}{\textsc{eq}}^{d}, \trianglelefteq _{d}\right) }$ . Having this we consider the following parametrized first-order slow well-partial-ordering sentence ${\sf{SWP}\left({\rm S}\text{\textsc{eq}}^{d}, \trianglelefteq _{d}, r\right):}$ $$\left( \forall K > 0 (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  6. Lars Kristiansen, Jan-Christoph Schlage-Puchta & Andreas Weiermann (2012). Streamlined Subrecursive Degree Theory. Annals of Pure and Applied Logic 163 (6):698-716.
  7. Andreas Weiermann & Alan R. Woods (2012). Some Natural Zero One Laws for Ordinals Below Ε 0. In S. Barry Cooper (ed.), How the World Computes. 723--732.
    Direct download  
     
    My bibliography  
     
    Export citation  
  8. Michael Rathjen & Andreas Weiermann (2011). Reverse Mathematics and Well-Ordering Principles. In S. B. Cooper & Andrea Sorbi (eds.), Computability in Context: Computation and Logic in the Real World. World Scientific.
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  9. Andreas Weiermann & Gunnar Wilken (2011). Ordinal Arithmetic with Simultaneously Defined Theta‐Functions. Mathematical Logic Quarterly 57 (2):116-132.
    This article provides a detailed comparison between two systems of collapsing functions. These functions play a crucial role in proof theory, in the analysis of patterns of resemblance, and the analysis of maximal order types of well partial orders. The exact correspondence given here serves as a starting point for far reaching extensions of current results on patterns and well partial orders. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.
    No categories
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  10. Eran Omri & Andreas Weiermann (2009). Classifying the Phase Transition Threshold for Ackermannian Functions. Annals of Pure and Applied Logic 158 (3):156-162.
    It is well known that the Ackermann function can be defined via diagonalization from an iteration hierarchy which is built on a start function like the successor function. In this paper we study for a given start function g iteration hierarchies with a sub-linear modulus h of iteration. In terms of g and h we classify the phase transition for the resulting diagonal function from being primitive recursive to being Ackermannian.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  11. Andreas Weiermann (2009). Phase Transitions for Gödel Incompleteness. Annals of Pure and Applied Logic 157 (2):281-296.
    Gödel’s first incompleteness result from 1931 states that there are true assertions about the natural numbers which do not follow from the Peano axioms. Since 1931 many researchers have been looking for natural examples of such assertions and breakthroughs were obtained in the seventies by Jeff Paris [Some independence results for Peano arithmetic. J. Symbolic Logic 43 725–731] , Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977] and Laurie Kirby [L. Kirby, Jeff Paris, Accessible independence results for Peano Arithmetic, Bull. of (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  12. Henryk Kotlarski, Bożena Piekart & Andreas Weiermann (2007). More on Lower Bounds for Partitioning Α-Large Sets. Annals of Pure and Applied Logic 147 (3):113-126.
    Continuing the earlier research from [T. Bigorajska, H. Kotlarski, Partitioning α-large sets: some lower bounds, Trans. Amer. Math. Soc. 358 4981–5001] we show that for the price of multiplying the number of parts by 3 we may construct partitions all of whose homogeneous sets are much smaller than in [T. Bigorajska, H. Kotlarski, Partitioning α-large sets: some lower bounds, Trans. Amer. Math. Soc. 358 4981–5001]. We also show that the Paris–Harrington independent statement remains unprovable if the number of colors is (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  13. Andreas Weiermann (2007). Phase Transition Thresholds for Some Friedman-Style Independence Results. Mlq 53 (1):4-18.
    We classify the phase transition thresholds from provability to unprovability for certain Friedman-style miniaturizations of Kruskal's Theorem and Higman's Lemma. In addition we prove a new and unexpected phase transition result for ε0. Motivated by renormalization and universality issues from statistical physics we finally state a universality hypothesis.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  14. Steve Awodey, Raf Cluckers, Ilijas Farah, Solomon Feferman, Deirdre Haskell, Andrey Morozov, Vladimir Pestov, Andre Scedrov, Andreas Weiermann & Jindrich Zapletal (2006). Stanford University, Stanford, CA March 19–22, 2005. Bulletin of Symbolic Logic 12 (1).
    Direct download  
     
    My bibliography  
     
    Export citation  
  15. Andreas Weiermann (2006). Classifying the Provably Total Functions of Pa. Bulletin of Symbolic Logic 12 (2):177-190.
    We give a self-contained and streamlined version of the classification of the provably computable functions of PA. The emphasis is put on illuminating as well as seems possible the intrinsic computational character of the standard cut elimination process. The article is intended to be suitable for teaching purposes and just requires basic familiarity with PA and the ordinals below ε0. (Familiarity with a cut elimination theorem for a Gentzen or Tait calculus is helpful but not presupposed).
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  16. Andreas Weiermann (2005). Analytic Combinatorics, Proof-Theoretic Ordinals, and Phase Transitions for Independence Results. Annals of Pure and Applied Logic 136 (1):189-218.
    This paper is intended to give for a general mathematical audience a survey of intriguing connections between analytic combinatorics and logic. We define the ordinals below ε0 in non-logical terms and we survey a selection of recent results about the analytic combinatorics of these ordinals. Using a versatile and flexible compression technique we give applications to phase transitions for independence results, Hilbert’s basis theorem, local number theory, Ramsey theory, Hydra games, and Goodstein sequences. We discuss briefly universality and renormalization issues (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  17. Andreas Weiermann (2004). Complexity Bounds for Some Finite Forms of Kruskal's Theorem. Bulletin of Symbolic Logic 10 (4):588-590.
     
    My bibliography  
     
    Export citation  
  18. Andreas Weiermann (2003). An Application of Graphical Enumeration to PA. Journal of Symbolic Logic 68 (1):5-16.
    For α less than ε0 let $N\alpha$ be the number of occurrences of ω in the Cantor normal form of α. Further let $\mid n \mid$ denote the binary length of a natural number n, let $\mid n\mid_h$ denote the h-times iterated binary length of n and let inv(n) be the least h such that $\mid n\mid_h \leq 2$ . We show that for any natural number h first order Peano arithmetic, PA, does not prove the following sentence: For all (...)
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  19. Benedikt Löwe, Florian Rudolph, Andreas Weiermann & Slow Versus Fast Growing (2002). Foundations of the Formal Sciences I. Synthese 133:463-464.
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  20. Andreas Weiermann (2002). Review: Toshiyasu Arai, Consistency Proof Via Pointwise Induction. [REVIEW] Bulletin of Symbolic Logic 8 (4):536-537.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  21. Andreas Weiermann (2002). Consistency Proof Via Pointwise Induction, Reviewed by Andreas Weiermann. [REVIEW] Bulletin of Symbolic Logic 8 (4):536-537.
     
    My bibliography  
     
    Export citation  
  22. Andreas Weiermann (2002). Slow Versus Fast Growing. Synthese 133 (1-2):13 - 29.
    We survey a selection of results about majorization hierarchies. The main focus is on classical and recent results about the comparison between the slow and fast growing hierarchies.
    No categories
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  23. Andreas Weiermann (2001). Γ0 May Be Minimal Subrecursively Inaccessible. Mathematical Logic Quarterly 47 (3):397-408.
    Let T be the standard Veblen 1908 ordinal notation system for Γ0 as defined, for example, in Schütte's 1977 textbook [13] on Proof Theory. We define a slight modification of the standard assignment of fundamental sequences for the limit ordinals in T and prove that Γ0 is subrecursively inaccessible for this assignment, i.e. the induced slow and fast growing hierarchy match up at Γ0 for the first time.The results of this paper also indicate that φε00 may be considered as a (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  24. Andreas Weiermann (2001). Some Interesting Connections Between the Slow Growing Hierarchy and the Ackermann Function. Journal of Symbolic Logic 66 (2):609-628.
    It is shown that the so called slow growing hierarchy depends non trivially on the choice of its underlying structure of ordinals. To this end we investigate the growth rate behaviour of the slow growing hierarchy along natural subsets of notations for Γ 0 . Let T be the set-theoretic ordinal notation system for Γ 0 and T tree the tree ordinal representation for Γ. It is shown in this paper that (G α ) α ∈ T matches up with (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  25. Arnold Beckmann & Andreas Weiermann (2000). Characterizing the Elementary Recursive Functions by a Fragment of Gödel's T. Archive for Mathematical Logic 39 (7):475-491.
    Let T be Gödel's system of primitive recursive functionals of finite type in a combinatory logic formulation. Let $T^{\star}$ be the subsystem of T in which the iterator and recursor constants are permitted only when immediately applied to type 0 arguments. By a Howard-Schütte-style argument the $T^{\star}$ -derivation lengths are classified in terms of an iterated exponential function. As a consequence a constructive strong normalization proof for $T^{\star}$ is obtained. Another consequence is that every $T^{\star}$ -representable number-theoretic function is elementary (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  26. Benjamin Blankertz & Andreas Weiermann (1999). A Uniform Approach for Characterizing the Provably Total Number-Theoretic Functions of KPM and (Some of) its Subsystems. Studia Logica 62 (3):399-427.
    In this article we show how to extract with the use of the Buchholz-Cichon-Weiermann approach to subrecursive hierarchies from Rathjen's 1991 ordinal analysis of KPM a characterization of the provably total number-theoretic functions of KPM and some of its (most prominent) subsystems in a uniform and direct way.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  27. Andreas Weiermann (1998). Bounding Derivation Lengths with Functions From the Slow Growing Hierarchy. Archive for Mathematical Logic 37 (5-6):427-441.
    Let $R$ be a (finite) rewrite system over a (finite) signature. Let $\succ$ be a strict well-founded termination ordering on the set of terms in question so that the rules of $R$ are reducing under $\succ$ . Then $R$ is terminating. In this article it is proved for a certain class of far reaching termination orderings (of order type reaching up to the first subrecursively inaccessible ordinal, i.e. the proof-theoretic ordinal of $ID_{<\omega}$ ) that – under some reasonable assumptions which (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  28. Andreas Weiermann (1998). How is It That Infinitary Methods Can Be Applied to Finitary Mathematics? Gödel's T: A Case Study. Journal of Symbolic Logic 63 (4):1348-1370.
    Inspired by Pohlers' local predicativity approach to Pure Proof Theory and Howard's ordinal analysis of bar recursion of type zero we present a short, technically smooth and constructive strong normalization proof for Gödel's system T of primitive recursive functionals of finite types by constructing an ε 0 -recursive function [] 0 : T → ω so that a reduces to b implies [a] $_0 > [b]_0$ . The construction of [] 0 is based on a careful analysis of the Howard-Schütte (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  29. E. A. Cichon & Andreas Weiermann (1997). Term Rewriting Theory for the Primitive Recursive Functions. Annals of Pure and Applied Logic 83 (3):199-223.
    The termination of rewrite systems for parameter recursion, simple nested recursion and unnested multiple recursion is shown by using monotone interpretations both on the ordinals below the first primitive recursively closed ordinal and on the natural numbers. We show that the resulting derivation lengths are primitive recursive. As a corollary we obtain transparent and illuminating proofs of the facts that the schemata of parameter recursion, simple nested recursion and unnested multiple recursion lead from primitive recursive functions to primitive recursive functions.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  30. Andreas Weiermann (1997). A Proof of Strongly Uniform Termination for Gödel's T by Methods From Local Predicativity. Archive for Mathematical Logic 36 (6):445-460.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  31. Andreas Weiermann (1997). Sometimes Slow Growing is Fast Growing. Annals of Pure and Applied Logic 90 (1-3):91-99.
    The slow growing hierarchy is commonly defined as follows: G0 = 0, Gx−1 := Gx + 1 and Gλ := Gλ[x] where λ<0 is a limit and ·[·]:0∩ Lim × ω → 0 is a given assignment of fundamental sequences for the limits below 0. The first obvious question which is encountered when one looks at this definition is: How does this hierarchy depend on the choice of the underlying system of fundamental sequences? Of course, it is well known and (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  32. Arnold Beckmann & Andreas Weiermann (1996). A Term Rewriting Characterization of the Polytime Functions and Related Complexity Classes. Archive for Mathematical Logic 36 (1):11-30.
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  33. Andreas Weiermann (1996). How to Characterize Provably Total Functions by Local Predicativity. Journal of Symbolic Logic 61 (1):52-69.
    Inspired by Pohlers' proof-theoretic analysis of KPω we give a straightforward non-metamathematical proof of the (well-known) classification of the provably total functions of $PA, PA + TI(\prec\lceil)$ (where it is assumed that the well-ordering $\prec$ has some reasonable closure properties) and KPω. Our method relies on a new approach to subrecursion due to Buchholz, Cichon and the author.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  34. Andreas Weiermann (1995). Investigations on Slow Versus Fast Growing: How to Majorize Slow Growing Functions Nontrivially by Fast Growing Ones. [REVIEW] 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 (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  35. Wilfried Buchholz, Adam Cichon & Andreas Weiermann (1994). A Uniform Approach to Fundamental Sequences and Hierarchies. Mathematical Logic Quarterly 40 (2):273-286.
    In this article we give a unifying approach to the theory of fundamental sequences and their related Hardy hierarchies of number-theoretic functions and we show the equivalence of the new approach with the classical one.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  36. Andreas Weiermann (1994). A Functorial Property of the Aczel-Buchholz-Feferman Function. Journal of Symbolic Logic 59 (3):945-955.
    Let Ω be the least uncountable ordinal. Let K(Ω) be the category where the objects are the countable ordinals and where the morphisms are the strictly monotonic increasing functions. A dilator is a functor on K(Ω) which preserves direct limits and pullbacks. Let $\tau \Omega: \xi = \omega^\xi\}$ . Then τ has a unique "term"-representation in Ω. λξη.ω ξ + η and countable ordinals called the constituents of τ. Let $\delta and K(τ) be the set of the constituents of τ. (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  37. Michael Rathjen & Andreas Weiermann (1993). Proof-Theoretic Investigations on Kruskal's Theorem. Annals of Pure and Applied Logic 60 (1):49-88.
    In this paper we calibrate the exact proof-theoretic strength of Kruskal's theorem, thereby giving, in some sense, the most elementary proof of Kruskal's theorem. Furthermore, these investigations give rise to ordinal analyses of restricted bar induction.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  38. Andreas Weiermann (1993). An Order‐Theoretic Characterization of the Schütte‐Veblen‐Hierarchy. Mathematical Logic Quarterly 39 (1):367-383.
    For f: On → On let supp: = ξ: 0, and let S := {f : On → On : supp finite}. For f,g ϵ S definef ≤ g : ↔ [h one-to-one ⁁ f ≤ g)].A function ψ : S → On is called monotonic increasing, if f≤ψ and if f ≤ g implies ψ ≤ ψ. For a mapping ψ : S → On let Clψ be the least set T of ordinals which contains 0 as an element (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  39. Andreas Weiermann (1993). A Simplified Functorial Construction of the Veblen Hierarchy. Mathematical Logic Quarterly 39 (1):269-273.
    We give a simple and elementary proof of the following result of Girard and Vauzeilles which is proved in [5]: “The binary Veblen function ψ: On × On — On is a dilator.” Our proof indicates the intimate connection between the traditional theory of ordinal notation systems and Girard's theory of denotation systems. MSC: 03F15.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  40. Andreas Weiermann (1993). Bounds for the Closure Ordinals of Essentially Monotonic Increasing Functions. Journal of Symbolic Logic 58 (2):664-671.
    Let $\Omega:= \aleph_1$ . For any $\alpha \Omega:\xi = \omega^\xi\}$ let EΩ (α) be the finite set of ε-numbers below Ω which are needed for the unique representation of α in Cantor-normal form using 0, Ω, +, and ω. Let $\alpha^\ast:= \max (E_\Omega(\alpha) \cup \{0\})$ . A function f: εΩ + 1 → Ω is called essentially increasing, if for any $\alpha < \varepsilon_{\Omega + 1}; f(\alpha) \geq \alpha^\ast: f$ is called essentially monotonic, if for any $\alpha,\beta < \varepsilon_{\Omega + (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  41. Andreas Weiermann (1991). Vereinfachte Kollabierungsfunktionen Und Ihre Anwendungen. Archive for Mathematical Logic 31 (2):85-94.
    In this article we define a new and transparent concept of total collapsing functions for an ordinal notation system which is characteristic for the theory (Δ 2 1 -CA)+(BI). We show that our construction allows the application of Pohler's method of local predicativity as presented in [2] which yields a perspicious proof-theoretic analysis of (Δ 2 1 -CA)+(BI) being not much more complicated than for ID1.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation