Veblen hierarchy

The Veblen hierarchy is a sequence of ordinal-indexed functions \( \varphi_\alpha: \mathrm{Ord} \to \mathrm{Ord} \) which extend Cantor normal form by beginning with the base function \( \alpha \mapsto \omega^\alpha \) and iteratively taking fixed points at each next step. Formally, letting \( \mathrm{AP} := \{\omega^\alpha: \alpha \in \mathrm{Ord}\} \), we can define \( \varphi_\alpha(\beta) := \min\{\zeta \in \mathrm{AP}: \forall \gamma ((\gamma < \alpha \rightarrow \varphi_\gamma(\zeta) = \zeta) \land (\gamma < \beta \rightarrow \varphi_\alpha(\gamma) < \zeta))\} \). This is a definition by transfinite recursion, and is well-defined by the transfinite recursion theorem.

The first stage of the Veblen hierarchy is just the function \( \alpha \mapsto \omega^\alpha \). Then the next stage, \( \varphi_1(\beta) \) (alternatively written \( \varphi(1,\beta) \)) enumerates the fixed points of the first stage - these are just the epsilon numbers. This continues to the zeta numbers, followed by the eta numbers, although this convention is rare. At the \( \omega \)th stage, since \( \omega - 1 \) doesn't exist, instead \( \varphi(\omega,\beta) \) enumerates the ordinals that are simultaneous fixed points of \( \alpha \mapsto \varphi(n,\beta) \) for all \( n < \omega \).

Analogously to Cantor normal form, every ordinal can be written in its Veblen normal form, as a sum \( \varphi_{\alpha_1}(\beta_1) + \varphi_{\alpha_2}(\beta_2) + \cdots + \varphi_{\alpha_n}(\beta_n) \). Like how the limit of hereditary CNF is \( \varepsilon_0 = \varphi_1(0) \), the limit of hereditary of hereditary VNF is known as \( \Gamma_0 \), aka the Feferman-Schütte ordinal. It is equal to a moderately powerful system of second-order arithmetic, containing a second-order analogue of Peano arithmetic known as arithmetical comprehension, with an additional axiom that allows one to do transfinite recursions. As such it has been described as the least truly impredicative ordinal - the least ordinal which truly can not described from below and any definition must involve some form of self-reference. However, this description has been challenged on multiple occassions.

Ordinals unreachable from below via binary Veblen normal form, the first of which is \( \Gamma_0 \), are typically known as gamma numbers or strongly critical ordinals. They are important in ordinal analysis due to the involvement of the Veblen function in cut-elimination. The enumeration function of the strongly critical ordinals is typically denoted \( \alpha \mapsto \Gamma_\alpha \), analogously to \( \alpha \mapsto \varepsilon_\alpha \) or \( \alpha \mapsto \zeta_\alpha \).

Ordinals beyond \( \Gamma_0 \) can be written using a variadic extension of the Veblen hierarchy. This extension takes the form of \(\varphi(...,\alpha_3,\alpha_2,\alpha_1,\alpha_0)\) for finite amounts of entries. This reaches the Small Veblen ordinal, and can be extended, through transfinite amounts of entries (formalized via finitely-supported functions on ordinals), to the Large Veblen ordinal, and through "rows" and "planes" of entries to reach the Bachmann-Howard ordinal, in which one allows taking fixed points of amounts of entries. However, for ordinals beyond the Large Veblen ordinal, ordinal collapsing functions are typically considered more efficient.