Source author record

Andreas Weiermann

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.LO math.CO Logic in Computer Science math.NT

Catalog footprint

Research overview

15works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

The fractal Goodstein principle

The original Goodstein process is based on writing numbers in hereditary $b$ -exponential normal form: that is, each number $n$ is written in some base $b\geq 2$ as $n=b^ea+r$ , with $e$ and $r$ iteratively being written in hereditary $b$ -exponential normal form. We define a new process which generalises the original by writing expressions in terms of a hierarchy of bases $B$ , instead of a single base $b$ . In particular, the `digit' $a$ may itself be written with respect to a smaller base $b'$ . We show that this new process always terminates, but termination is independent of Kripke-Platek set theory, or other theories of Bachmann-Howard strength.

preprint2024arXiv

Fundamental sequences and fast-growing hierarchies for the Bachmann-Howard ordinal

We prove that Buchholz's system of fundamental sequences for the $\vartheta$ function enjoys various regularity conditions, including the Bachmann property. We partially extend these results to variants of the $\vartheta$ function, including a version without addition for countable ordinals. We conclude that the Hardy functions based on these notation systems enjoy natural monotonicity properties and majorize all functions defined by primitive recursion along $\vartheta(\varepsilon_{Ω+1})$ .

preprint2022arXiv

Arithmetical and Hyperarithmetical Worm Battles

Japaridze's provability logic $GLP$ has one modality $[n]$ for each natural number and has been used by Beklemishev for a proof theoretic analysis of Peano aritmetic $(PA)$ and related theories. Among other benefits, this analysis yields the so-called Every Worm Dies $(EWD)$ principle, a natural combinatorial statement independent of $PA$ . Recently, Beklemishev and Pakhomov have studied notions of provability corresponding to transfinite modalities in $GLP$ . We show that indeed the natural transfinite extension of $GLP$ is sound for this interpretation, and yields independent combinatorial principles for the second order theory $ACA$ of arithmetical comprehension with full induction. We also provide restricted versions of $EWD$ related to the fragments $IΣ_n$ of Peano arithmetic. In order to prove the latter, we show that standard Hardy functions majorize their variants based on tree ordinals.

preprint2022arXiv

Fast Goodstein Walks

We define a variant of the Goodstein process based on fast-growing functions and show that it terminates, but this fact is not provable in Kripke-Platek set theory or other theories of strength the Bachmann-Howard ordinal. We moreover show that this Goodstein process is of maximal length, so that any alternative Goodstein process based on the same fast-growing functions will also terminate.

preprint2022arXiv

Intermediate Goodstein principles

The original Goodstein process proceeds by writing natural numbers in nested exponential $k$ -normal form, then successively raising the base to $k+1$ and subtracting one from the end result. Such sequences always reach zero, but this fact is unprovable in Peano arithmetic. In this paper we instead consider notations for natural numbers based on the Ackermann function. We define three new Goodstein processes, obtaining new independence results for ${\sf ACA}_0$ , ${\sf ACA}_0'$ and ${\sf ACA}_0^+$ , theories of second order arithmetic related to the existence of Turing jumps.

preprint2020arXiv

Giant and illusionary giant Goodstein principles

We analyze several natural Goodstein principles which themselves are defined with respect to the Ackermann function and the extended Ackermann function. These Ackermann functions are well established canonical fast growing functions labeled by ordinals not exceeding $\varepsilon_0$ . Among the Goodsteinprinciples under consideration, the giant ones, will be proof-theoretically strong (being unprovable in $\mathrm{PA}$ in the Ackermannian case and being unprovable in $\mathrm{ID}_1$ in the extended Ackermannian case) whereas others, the illusionary giant ones, will turn out to be comparatively much much weaker although they look strong at first sight.

preprint2020arXiv

Minimal bad sequences are necessary for a uniform Kruskal theorem

The minimal bad sequence argument due to Nash-Williams is a powerful tool in combinatorics with important implications for theoretical computer science. In particular, it yields a very elegant proof of Kruskal's theorem. At the same time, it is known that Kruskal's theorem does not require the full strength of the minimal bad sequence argument. This claim can be made precise in the framework of reverse mathematics, where the existence of minimal bad sequences is equivalent to a principle known as $Π^1_1$ -comprehension, which is much stronger than Kruskal's theorem. In the present paper we give a uniform version of Kruskal's theorem by relativizing it to certain transformations of well partial orders. We show that $Π^1_1$ -comprehension is equivalent to our uniform Kruskal theorem (over $\mathbf{RCA}_0$ together with the chain-antichain principle). This means that any proof of the uniform Kruskal theorem must entail the existence of minimal bad sequences. As a by-product of our investigation, we obtain uniform proofs of several Kruskal-type independence results.

preprint2020arXiv

Monadic second order limit laws for natural well orderings

By combining classical results of Büchi, some elementary Tauberian theorems and some basic tools from logic and combinatorics we show that every ordinal $α$ with $\varepsilon_0\geq α\geq ω^ω$ satisfies a natural monadic second order limit law and that every ordinal $α$ with $ω^ω>α\geq ω$ satisfies a natural monadic second order Cesaro limit law. In both cases we identify as usual $α$ with the class of substructures $\{β:β<α\}$ . We work in an additive setting where the norm function $N$ assigns to every ordinal $α$ the number of occurrrences of the symbol $ω$ in its Cantor normal form. This number is the same as the number of edges in the tree which is canonically associated with $α$ . For a given $α$ with $ω\leq α\leq \varepsilon_0$ the asymptotic probability of a monadic second order formula $φ$ from the language of linear orders is $\lim_{n\to\infty} \frac{\#\{β<α: Nβ=n\wedge β\models Φ\}}{\#\{β<α: Nβ=n\}}$ if this limit exists. If this limit exists only in the Cesaro sense we speak of the Cesaro asympotic probability of $φ$ . Moreover we prove monadic second order limit laws for the ordinal segments below below $Γ_0$ (where the norm function is extended appropriately) and we indicate how this paper's results can be extended to larger ordinal segments and even to certain impredicative ordinal notation systems having notations for uncountable ordinals. We also briefly indicate how to prove the corresponding multiplicative results for which the setting is defined relative to the Matula coding. The results of this paper concerning ordinals not exceeding $\varepsilon_0$ have been obtained partly in joint work with Alan R. Woods.

preprint2015arXiv

An order-theoretic characterization of the Howard-Bachmann-hierarchy

In this article we provide an intrinsic characterization of the famous Howard-Bachmann ordinal in terms of a natural well-partial-ordering by showing that this ordinal can be realized as a maximal order type of a class of generalized trees with respect to a homeomorphic embeddability relation. We use our calculations to draw some conclusions about some corresponding subsystems of second order arithmetic. All these subsystems deal with versions of light-face $Π^1_1$ -comprehension

preprint2015arXiv

Ordinal notation systems corresponding to Friedman's linearized well-partial-orders with gap-condition

In this article we investigate whether the addition-free theta functions form a canonical notation system for the linear versions of Friedman's well-partial-orders with the so-called gap-condition over a finite set of labels. Rather surprisingly, we can show this is the case for two labels, but not for more than two labels. To this end, we determine the order type of the notation systems for addition-free theta functions in terms of ordinals less than $\varepsilon_0$ . We further show that the maximal order type of the Friedman ordering can be obtained by a certain ordinal notation system which is based on specific binary theta functions.

preprint2013arXiv

Asymptotic distribution of integers with certain prime factorizations

Let $p_{1}<p_2<... <p_ν<...$ be the sequence of prime numbers and let $m$ be a positive integer. We give a strong asymptotic formula for the distribution of the set of integers having prime factorizations of the form $p_{m^{k_1}}p_{m^{k_{2}}...p_{m^{k_{n}}}$ with $k_{1}\le k_{2}\le...\le k_{n}$ . Such integers originate in various combinatorial counting problems; when $m=2$ , they arise as Matula numbers of certain rooted trees.

preprint2012arXiv

A Simplified Characterisation of Provably Computable Functions of the System ID_1 of Inductive Definitions

We present a simplified and streamlined characterisation of provably total computable functions of the theory ID_1 of non-iterated inductive definitions. The idea of the simplification is to employ the method of operator-controlled derivations that was originally introduced by Wilfried Buchholz and afterwards applied by the second author to a characterisation of provably total computable functions of Peano arithmetic PA.

preprint2012arXiv

Derivation Lengths Classification of Gödel's T Extending Howard's Assignment

Let T be Goedel's system of primitive recursive functionals of finite type in the lambda formulation. We define by constructive means using recursion on nested multisets a multivalued function I from the set of terms of T into the set of natural numbers such that if a term a reduces to a term b and if a natural number I(a) is assigned to a then a natural number I(b) can be assigned to b such that I(a) is greater than I(b). The construction of I is based on Howard's 1970 ordinal assignment for T and Weiermann's 1996 treatment of T in the combinatory logic version. As a corollary we obtain an optimal derivation length classification for the lambda formulation of T and its fragments. Compared with Weiermann's 1996 exposition this article yields solutions to several non-trivial problems arising from dealing with lambda terms instead of combinatory logic terms. It is expected that the methods developed here can be applied to other higher order rewrite systems resulting in new powerful termination orderings since T is a paradigm for such systems.

preprint2010arXiv

Partitioning $α$ -large sets for $α<\varepsilon_ω$

We generalise the results by Bigorajska and Kotlarski about partitioning $α$ -large sets, by extending the domain up to ordinals below $\varepsilon_ω$ . These results will be very useful to give a miniaturisation of the infinite Ramsey Theorem.

preprint2007arXiv

Unprovability results involving braids

We construct long sequences of braids that are descending with respect to the standard order of braids (``Dehornoy order''), and we deduce that, contrary to all usual algebraic properties of braids, certain simple combinatorial statements involving the braid order are true, but not provable in the subsystems ISigma1 or ISigma2 of the standard Peano system.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Andreas Weiermann

Research overview

Is this your work?

15 publications

The fractal Goodstein principle

Fundamental sequences and fast-growing hierarchies for the Bachmann-Howard ordinal

Arithmetical and Hyperarithmetical Worm Battles

Fast Goodstein Walks

Intermediate Goodstein principles

Giant and illusionary giant Goodstein principles

Minimal bad sequences are necessary for a uniform Kruskal theorem

Monadic second order limit laws for natural well orderings

An order-theoretic characterization of the Howard-Bachmann-hierarchy

Ordinal notation systems corresponding to Friedman's linearized well-partial-orders with gap-condition

Asymptotic distribution of integers with certain prime factorizations

A Simplified Characterisation of Provably Computable Functions of the System ID_1 of Inductive Definitions

Derivation Lengths Classification of Gödel's T Extending Howard's Assignment

Partitioning $α$ -large sets for $α<\varepsilon_ω$

Unprovability results involving braids

See the researcher in context

Building this map preview

Andreas Weiermann

Research overview

Is this your work?

15 publications

The fractal Goodstein principle

Fundamental sequences and fast-growing hierarchies for the Bachmann-Howard ordinal

Arithmetical and Hyperarithmetical Worm Battles

Fast Goodstein Walks

Intermediate Goodstein principles

Giant and illusionary giant Goodstein principles

Minimal bad sequences are necessary for a uniform Kruskal theorem

Monadic second order limit laws for natural well orderings

An order-theoretic characterization of the Howard-Bachmann-hierarchy

Ordinal notation systems corresponding to Friedman's linearized well-partial-orders with gap-condition

Asymptotic distribution of integers with certain prime factorizations

A Simplified Characterisation of Provably Computable Functions of the System ID_1 of Inductive Definitions

Derivation Lengths Classification of Gödel's T Extending Howard's Assignment

Partitioning ααα-large sets for α<εωα<\varepsilon_ωα<εω​

Unprovability results involving braids

See the researcher in context

Building this map preview

Partitioning $α$ -large sets for $α<\varepsilon_ω$