Functorial Fast-Growing Hierarchies

DOI10.1017/FMS.2023.128MaRDI QIDQ6148467zbMATH OpenOpenAlexFDO

Authors Juan P. Aguilera, Fedor N. Pakhomov, Andreas Weiermann

Publication date 7 February 2024

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Recursive ordinals and ordinal notations (03F15) Second- and higher-order arithmetic and fragments (03F35) Foundations, relations to logic and deductive systems (18A15) Preorders, orders, domains and lattices (viewed as categories) (18B35)

Abstract: Fast-growing hierarchies are sequences of functions obtained through various processes similar to the ones that yield multiplication from addition, exponentiation from multiplication, etc. We observe that fast-growing hierarchies can be naturally extended to functors on the categories of natural numbers and of linear orders. We show that the categorical extensions of binary fast-growing hierarchies to ordinals are isomorphic to denotation systems given by ordinal collapsing functions, thus establishing a connection between two fundamental concepts in Proof Theory. Using this fact, we obtain a restatement of the subsystem $P{i}_1^1$-CA${}_0$ of analysis as a higher-type wellordering principle.

Cites work

• \(\Pi_1^1\)-comprehension as a well-ordering principle
• A Uniform Approach to Fundamental Sequences and Hierarchies
• Accessible Recursive Functions
• Ackermann and Goodstein go functorial
• An independence result for \((\Pi^ 1_ 1-CA)+BI\)
• scientific article; zbMATH DE number 4033738 (Why is no real title available?)
• scientific article; zbMATH DE number 3472038 (Why is no real title available?)
• scientific article; zbMATH DE number 1390277 (Why is no real title available?)
• scientific article; zbMATH DE number 3061667 (Why is no real title available?)
• Long finite sequences
• Mathematics and computer science: coping with finiteness
• On the interpretation of non-finitist proofs–Part II
• Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy
• Ramsey's Theorem for n-Parameter Sets
• Reverse mathematics and ordinal exponentiation
• Reverse mathematics and well-ordering principles
• Reverse mathematics and well-ordering principles: a pilot study
• The Veblen functions for computability theorists
• Well-ordering principles and bar induction
• Π12-logic, Part 1: Dilators

Cited in

(2)

• On inverse Goodstein sequences
• The total set-recursive functions of \textsf{KPI} and related systems

This page was built for publication: Functorial Fast-Growing Hierarchies

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