Predicatively unprovable termination of the Ackermannian Goodstein process

DOI10.1090/PROC/14813zbMATH Open1484.03125arXiv1906.00020OpenAlexW2982685337WikidataQ126862778 ScholiaQ126862778MaRDI QIDQ5113418FDOQ5113418

Toshiyasu Arai, Stanley S. Wainer, David Fernández-Duque, Andreas Weiermann

Publication date: 11 June 2020

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

Abstract: 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 variant based on the Ackermann function. We show that Ackermannian Goodstein sequences eventually terminate, but this fact is not provable using predicative means.

Full work available at URL: https://arxiv.org/abs/1906.00020

Mathematics Subject Classification ID

Computability and recursion theory on ordinals, admissible sets, etc. (03D60) First-order arithmetic and fragments (03F30) Gödel numberings and issues of incompleteness (03F40) Recursive functions and relations, subrecursive hierarchies (03D20)

Cites Work

• Title not available (Why is that?)
• The consistency of arithmetics
• Proof theory. The first step into impredicativity
• Independence of Ramsey theorem variants using \(\varepsilon _0\)
• Systems of predicative analysis
• Title not available (Why is that?)
• Harvey Friedman's research on the foundations of mathematics
• Systems of predicative analysis, II: Representations of ordinals
• On the restricted ordinal theorem
• Some interesting connections between the slow growing hierarchy and the Ackermann function
• Accessible Independence Results for Peano Arithmetic
• A Uniform Approach to Fundamental Sequences and Hierarchies
• A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods
• Transfinite ordinals in recursive number theory
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
• Title not available (Why is that?)
• Classifying the Provably Total Functions of PA
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sharp phase transition thresholds for the Paris Harrington Ramsey numbers for a fixed dimension
• ACKERMANNIAN GOODSTEIN PRINCIPLES FOR FIRST ORDER PEANO ARITHMETIC
• Ramsey’s theorem for 𝑛-dimensional arrays

Cited In (5)

• GOODSTEIN SEQUENCES BASED ON A PARAMETRIZED ACKERMANN–PÉTER FUNCTION
• Ackermannian Goodstein sequences of intermediate growth
• Ackermann and Goodstein go functorial
• A walk with Goodstein and Ackermann
• A WALK WITH GOODSTEIN

   Recommendations

• A proof of strongly uniform termination for Gödel's \(T\) by methods from local predicativity 👍 👎
• Random unary predicates: Almost sure theories and countable models 👍 👎
• Nonaxiomatisability of equivalences over finite state processes 👍 👎
• Undecidable equivalences for basic process algebra 👍 👎
• Title not available (Why is that?) 👍 👎
• Deductive proofs of almost sure persistence and recurrence properties 👍 👎
• Proving finiteness of CCS processes by non-standard semantics 👍 👎
• Coinductive Proof Principles for Stochastic Processes 👍 👎
• Lifting non-finite axiomatizability results to extensions of process algebras 👍 👎
• Testing Finitary Probabilistic Processes 👍 👎

This page was built for publication: Predicatively unprovable termination of the Ackermannian Goodstein process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113418)