7 papers · 1 filter
Functorial Fast-Growing Hierarchies
J. P. Aguilera, F. Pakhomov, A. Weiermann
Fast-growing hierarchies are sequences of functions obtained through various processes similar to the ones that yield multiplication from addition, exponentiation from multiplicati…
Ackermann and Goodstein go functorial
Juan P. Aguilera, Anton Freund, Michael Rathjen +1
We present variants of Goodstein's theorem that are equivalent to arithmetical comprehension and to arithmetical transfinite recursion, respectively, over a weak base theory. These…
Monadic second order limit laws for natural well orderings
Andreas Weiermann
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…
Giant and illusionary giant Goodstein principles
Andreas Weiermann
We analyze several natural Goodstein principles which themselves are defined with respect to the Ackermann function and the extended Ackermann function. These Ackermann functions a…
Minimal bad sequences are necessary for a uniform Kruskal theorem
Anton Freund, Michael Rathjen, Andreas Weiermann
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…
Predicatively unprovable termination of the Ackermannian Goodstein process
Toshiyasu Arai, David Fernández-Duque, Stanley Wainer +1
The classical Goodstein process gives rise to long but finite sequences of natural numbers whose termination is not provable in Peano arithmetic. In this manuscript we consider a v…