Functorial Fast-Growing Hierarchies
Open Access
- 26 January 2024
- journal article
- research article
- Published by Cambridge University Press (CUP) in Forum of Mathematics, Sigma
- Vol. 12, e15
Abstract
We prove an isomorphism theorem between the canonical denotation systems for large natural numbers and large countable ordinal numbers, linking two fundamental concepts in Proof Theory. The first one is fast-growing hierarchies. These are sequences of functions on $\mathbb {N}$ obtained through processes such as the ones that yield multiplication from addition, exponentiation from multiplication, etc. and represent the canonical way of speaking about large finite numbers. The second one is ordinal collapsing functions, which represent the best-known method of describing large computable ordinals. We observe that fast-growing hierarchies can be naturally extended to functors on the categories of natural numbers and of linear orders. The isomorphism theorem asserts that the categorical extensions of binary fast-growing hierarchies to ordinals are isomorphic to denotation systems given by cardinal collapsing functions. As an application of this fact, we obtain a restatement of the subsystem $\Pi ^1_1$ - ${\mathsf {CA_0}}$ of analysis as a higher-type well-ordering principle asserting that binary fast-growing hierarchies preserve well-foundedness.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Reverse mathematics and well-ordering principles: A pilot studyAnnals of Pure and Applied Logic, 2009
- Long Finite SequencesJournal of Combinatorial Theory, Series A, 2001
- Reverse mathematics and ordinal exponentiationAnnals of Pure and Applied Logic, 1994
- A Uniform Approach to Fundamental Sequences and HierarchiesMathematical Logic Quarterly, 1994
- An independence result for (II11-CA)+BIAnnals of Pure and Applied Logic, 1987
- Mathematical GamesScientific American, 1977
- Mathematics and Computer Science: Coping with FinitenessScience, 1976
- Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchyThe Journal of Symbolic Logic, 1972
- Infinitary properties, local functors, and systems of ordinal functions1972
- On the interpretation of non-finitist proofs–Part IIThe Journal of Symbolic Logic, 1952