Slow-Growing Hierarchy¶

Builds an ordinal-indexed family of natural-number functions by successor increments and fundamental-sequence descent at limits.

Version: v1 · 2026-08-30 · History
Domain-specific #: 2793
Origin domain: proof theory
Subdomain: ordinal analysis

Core Idea¶

The Slow-Growing Hierarchy is an ordinal-indexed family of functions

\[ G_\alpha:\mathbb N\longrightarrow\mathbb N \]

generated by an exceptionally spare transfinite recursion. Fix an ordinal notation domain and, for each represented limit ordinal \(\lambda\), a fundamental sequence \(\lambda[0]<\lambda[1]<\cdots<\lambda\) cofinal in \(\lambda\). Then define

\[ G_0(n)=0,\qquad G_{\alpha+1}(n)=G_\alpha(n)+1,\qquad G_\lambda(n)=G_{\lambda[n]}(n). \]

Thus a successor index contributes one, while a limit index uses the input \(n\) to choose a smaller ordinal approximant and continues there. Gallier describes this as an outer-iteration hierarchy obtained from the successor base function. The name identifies this construction, not every family that informally grows slowly.

Scope of Application¶

The hierarchy belongs primarily to proof theory and ordinal analysis, where ordinal-indexed function families calibrate the strength of formal systems, majorize provably total functions, and translate ordinal information into finite numerical growth. Cichon and Wainer use slow-growing and related hierarchies to connect ordinal notations with computational classifications.

It also appears in computability and subrecursive complexity. There, the question is not merely how fast one row grows, but which familiar class a range of rows exhausts or majorizes, and how that answer changes when the fundamental-sequence system changes. Weiermann's comparison between standard and norm-based sequences is a particularly clear case.

Clarity¶

The hierarchy makes a potentially confusing source of growth explicit. To understand a value \(G_\alpha(n)\), ask two different questions: how many successor increments occur, and which limit approximants are selected on the way down? The recurrence answers both. It also prevents the phrase “indexed by \(\alpha\)” from hiding the role of \(n\): the same natural number is a function input and the diagonal selector at every encountered limit.

Manages Complexity¶

Ordinal notation can encode a vast nested recursion, yet the hierarchy compresses its finite behavior into three local rules. Instead of separately defining a function for each successor, power of \(\omega\), or higher limit, one supplies a uniform limit-descent interface. Fundamental sequences then turn a transfinite index into a finite computation for each fixed input, because every recursive call uses a smaller notation.

Abstract Reasoning¶

The structural signature licenses several useful inferences.

For a finite ordinal \(m\), repeated successor reduction gives \(G_m(n)=m\), independently of \(n\).
Under the standard convention \(\omega[n]=n\), \(G_\omega(n)=G_n(n)=n\).
A successor offset has a transparent additive effect: \(G_{\alpha+k}(n)=G_\alpha(n)+k\) for finite \(k\).
A disputed limit value should be diagnosed at the first limit descent; successor arithmetic cannot explain a disagreement created by distinct \(\lambda[n]\) assignments.
Claims about eventual domination require a fixed assignment and comparison notion.

Knowledge Transfer¶

Within proof theory, the exact pattern transfers among ordinal analyses, majorization results, termination bounds, and classifications of provably recursive functions. A proof written for a regular family of fundamental sequences can often be reused after verifying the new system's descent, cofinality, and coherence conditions. What transfers is a disciplined interface: base, successor, limit selector, and comparison regime.

Relationships to Other Abstractions¶

Current abstraction Slow-Growing Hierarchy Domain-specific

Parents (3) — more general patterns this builds on

Slow-Growing Hierarchy is a kind of Hierarchy Prime

Slow-Growing Hierarchy is a strict specialization of Hierarchy: its rows are levels indexed by ordinal notations, and its differentia are the three recursive clauses and fundamental-sequence dependence.
Slow-Growing Hierarchy presupposes Recursion Prime

Slow-Growing Hierarchy is a strict specialization of Hierarchy: its rows are levels indexed by ordinal notations, and its differentia are the three recursive clauses and fundamental-sequence dependence.
Slow-Growing Hierarchy presupposes Well-Foundedness (Well-Ordering) Prime

The accepted reference-grade review places Slow-Growing Hierarchy under Well-Foundedness (Well-Ordering) because the child instantiates or depends on the parent's broader structure while retaining its own constitutive identity.

Hierarchy paths (11) — routes to 7 parentless roots

Slow-Growing Hierarchy → Hierarchy → Network → Reservoir-Flux Network → Conservation Laws → Invariance

Neighborhood in Abstraction Space¶

Slow-Growing Hierarchy sits in a sparse region of the domain-specific corpus (73^rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Core Data Structures & Testing (6 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08