Skip to content

Slow-Growing Hierarchy

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

Version
v2 · 2026-09-19 · History
Domain-specific #
2793
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomains
Proof Theory, Ordinal Analysis → Mathematics

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

Local relationship map for Slow-Growing HierarchyParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Slow-GrowingHierarchyDOMAINPrime abstraction: Recursion — presupposesRecursionPRIMEPrime abstraction: Well-Foundedness (Well-Ordering) — presupposesWell-Foundedness(Well-Ordering)PRIMEPrime abstraction: Hierarchy — is a kind ofHierarchyPRIME

Current abstraction Slow-Growing Hierarchy Domain-specific

Parents (3) — outgoing typed relations

  • 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

Neighborhood in Abstraction Space

Slow-Growing Hierarchy sits in a moderately populated region (55th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25