Veblen function

In mathematics, the Veblen functions are a hierarchy of normal functions (continuous strictly increasing functions from ordinals to ordinals), introduced by Oswald Veblen in Veblen (1908). If φ₀ is any normal function, then for any non-zero ordinal α, φ_α is the function enumerating the common fixed points of φ_β for β<α. These functions are all normal.

The Veblen hierarchy

In the special case when φ₀(α)=ω^α this family of functions is known as the Veblen hierarchy. The function φ₁ is the same as the ε function: φ₁(α)= ε_α. If $\alpha < \beta \,,$ then $\varphi_{\alpha}(\varphi_{\beta}(\gamma)) = \varphi_{\beta}(\gamma) \,.$ From this and the fact that φ_β is strictly increasing we get the ordering: $\varphi_\alpha(\beta) < \varphi_\gamma(\delta) \,$ if and only if either ($\alpha = \gamma \,$ and $\beta < \delta \,$) or ($\alpha < \gamma \,$ and $\beta < \varphi_\gamma(\delta) \,$) or ($\alpha > \gamma \,$ and $\varphi_\alpha(\beta) < \delta \,$).

Fundamental sequences for the Veblen hierarchy

The fundamental sequence for an ordinal with cofinality ω is a distinguished strictly increasing ω-sequence which has the ordinal as its limit. If one has fundamental sequences for α and all smaller limit ordinals, then one can create an explicit constructive bijection between ω and α, (i.e. one not using the axiom of choice). Here we will describe fundamental sequences for the Veblen hierarchy of ordinals. The image of n under the fundamental sequence for α will be indicated by α[n].

A variation of Cantor normal form used in connection with the Veblen hierarchy is — every nonzero ordinal number α can be uniquely written as $\alpha = \varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k)$, where k>0 is a natural number and each term after the first is less than or equal to the previous term, $\varphi_{\beta_m}(\gamma_m) \geq \varphi_{\beta_{m+1}}(\gamma_{m+1}) \,,$ and each $\gamma_m < \varphi_{\beta_m}(\gamma_m) \,.$ If a fundamental sequence can be provided for the last term, then that term can be replaced by such a sequence to get $\alpha [n] = \varphi_{\beta_1}(\gamma_1) + \cdots + \varphi_{\beta_{k-1}}(\gamma_{k-1}) + (\varphi_{\beta_k}(\gamma_k) [n]) \,.$

For any β, if γ is a limit with $\gamma < \varphi_{\beta} (\gamma) \,,$ then let $\varphi_{\beta}(\gamma) [n] = \varphi_{\beta}(\gamma [n]) \,.$

No such sequence can be provided for φ₀(0) = ω⁰ = 1 because it does not have cofinality ω.

For $\varphi_0(\gamma+1) = \omega ^{\gamma+1} = \omega^ \gamma \cdot \omega \,,$ we choose $\varphi_0(\gamma+1) [n] = \varphi_0(\gamma) \cdot n = \omega^{\gamma} \cdot n \,.$

For $\varphi_{\beta+1}(0) \,,$ we use $\varphi_{\beta+1}(0) [0] = 0 \,$ and $\varphi_{\beta+1}(0) [n+1] = \varphi_{\beta}(\varphi_{\beta+1}(0) [n]) \,,$ i.e. 0, φ_β(0), φ_β(φ_β(0)), etc..

For φ_{β + 1}(γ + 1), we use $\varphi_{\beta+1}(\gamma+1) [0] = \varphi_{\beta+1}(\gamma)+1 \,$ and $\varphi_{\beta+1}(\gamma+1) [n+1] = \varphi_{\beta} (\varphi_{\beta+1}(\gamma+1) [n]) \,.$

Now suppose that β is a limit:

If β < φ_β(0), then let $\varphi_{\beta}(0) [n] = \varphi_{\beta [n]}(0) \,.$

For φ_β(γ + 1), use $\varphi_{\beta}(\gamma+1) [n] = \varphi_{\beta [n]}(\varphi_{\beta}(\gamma)+1) \,.$

Otherwise, the ordinal cannot be described in terms of smaller ordinals using φ and this scheme does not apply to it.

The Γ function

The function Γ enumerates the ordinals α such that φ_α(0) = α. Γ₀ is the Feferman–Schütte ordinal, i.e. it is the smallest α such that φ_α(0) = α.

For Γ₀, a fundamental sequence could be chosen to be $\Gamma_0 [0] = 0 \,$ and $\Gamma_0 [n+1] = \varphi_{\Gamma_0 [n]} (0) \,.$

For Γ_β+1, let $\Gamma_{\beta+1} [0] = \Gamma_{\beta} + 1 \,$ and $\Gamma_{\beta+1} [n+1] = \varphi_{\Gamma_{\beta+1} [n]} (0) \,.$

For Γ_β where $\beta < \Gamma_{\beta} \,$ is a limit, let $\Gamma_{\beta} [n] = \Gamma_{\beta [n]} \,.$

Generalizations

In this section it is more convenient to think of φ_α(β) as a function φ(α,β) of two variables. Veblen showed how to generalize the definition to produce a function φ(α_n,α_n-1, ...,α₀) of several variables. More generally he showed that φ can be defined even for a transfinite sequence of ordinals α_β, provided that all but a finite number of them are zero. Notice that if such a sequence of ordinals is chosen from those less than an uncountable regular cardinal κ, then the sequence may be encoded as a single ordinal less than κ^κ. So one is defining a function φ from κ^κ into κ.

References

• Hilbert Levitz, Transfinite Ordinals and Their Notations: For The Uninitiated, expository article (8 pages, in PostScript)
• Pohlers, Wolfram (1989), Proof theory, Lecture Notes in Mathematics, 1407, Berlin: Springer-Verlag, ISBN 3-540-51842-8, MR1026933 
• Schütte, Kurt (1977), Proof theory, Grundlehren der Mathematischen Wissenschaften, 225, Berlin-New York: Springer-Verlag, pp. xii+299, ISBN 3-540-07911-4, MR0505313 
• Takeuti, Gaisi (1987), Proof theory, Studies in Logic and the Foundations of Mathematics, 81 (Second ed.), Amsterdam: North-Holland Publishing Co., ISBN 0-444-87943-9, MR0882549 
• Smorynski, C. (1982), "The varieties of arboreal experience", Math. Intelligencer 4 (4): 182–189, doi:10.1007/BF03023553  contains an informal description of the Veblen hierarchy.
• Veblen, Oswald (1908), "Continuous Increasing Functions of Finite and Transfinite Ordinals", Transactions of the American Mathematical Society 9 (3): 280–292, doi:10.2307/1988605, JSTOR 1988605 
• Miller, Larry W. (1976), "Normal Functions and Constructive Ordinal Notations", The Journal of Symbolic Logic 41 (2): 439–459, doi:10.2307/2272243, JSTOR 2272243