Predicatively unprovable termination of the Ackermannian Goodstein process

DOI10.1090/PROC/14813MaRDI QIDQ5113418zbMATH OpenOpenAlexWikidataFDO

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

Publication date 11 June 2020

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

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)

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.

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
• scientific article; zbMATH DE number 2163042
• 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

Cites work

• scientific article; zbMATH DE number 4033742 (Why is no real title available?)
• scientific article; zbMATH DE number 1215495 (Why is no real title available?)
• scientific article; zbMATH DE number 2152691 (Why is no real title available?)
• scientific article; zbMATH DE number 862507 (Why is no real title available?)
• A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods
• A Uniform Approach to Fundamental Sequences and Hierarchies
• Accessible Independence Results for Peano Arithmetic
• Ackermannian Goodstein principles for first order Peano arithmetic
• Classifying the Provably Total Functions of PA
• Harvey Friedman's research on the foundations of mathematics
• Independence of Ramsey theorem variants using \(\varepsilon _0\)
• On the restricted ordinal theorem
• Proof theory. The first step into impredicativity
• Ramsey’s theorem for 𝑛-dimensional arrays
• Sharp phase transition thresholds for the Paris Harrington Ramsey numbers for a fixed dimension
• Some interesting connections between the slow growing hierarchy and the Ackermann function
• Subsystems of second order arithmetic
• Systems of predicative analysis
• Systems of predicative analysis, II: Representations of ordinals
• The consistency of arithmetics
• Transfinite ordinals in recursive number theory
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I

Cited in

(11)

• Ackermannian Goodstein sequences of intermediate growth
• GOODSTEIN SEQUENCES BASED ON A PARAMETRIZED ACKERMANN–PÉTER FUNCTION
• Ackermannian Goodstein principles for first order Peano arithmetic
• Ackermann and Goodstein go functorial
• A walk with Goodstein and Ackermann
• Intermediate Goodstein Principles
• scientific article; zbMATH DE number 3912360 (Why is no real title available?)
• A WALK WITH GOODSTEIN
• On inverse Goodstein sequences
• Extensions of arithmetic for proving termination of computations
• Beyond Peano arithmetic -- automatically proving termination of the Goodstein sequence

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)