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 $\varphi _{0}(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, $\varphi _{{\beta }}(0)$, $\varphi _{{\beta }}(\varphi _{{\beta }}(0))$, etc..

For $\varphi _{{\beta +1}}(\gamma +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 $\beta <\varphi _{{\beta }}(0)$, then let $\varphi _{{\beta }}(0)[n]=\varphi _{{\beta [n]}}(0)\,.$

For $\varphi _{{\beta }}(\gamma +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 $\varphi$ 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

Finitely many variables

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, namely:

• φ(α)=ω^α for a single variable,
• φ(0,α_n−1,…,α₀)=φ(α_n−1,…,α₀), and
• for α>0, γ↦φ(α_n,…,α_i+1,α,0,…,0,γ) is the function enumerating the common fixed points of the functions ξ↦φ(α_n,…,α_i+1,β,ξ,0,…,0) for all β<α.

For example, φ(1,0,γ) is the γ-th fixed point of the functions ξ↦φ(ξ,0), namely Γ_γ; then φ(1,1,γ) enumerates the fixed points of that function, i.e., of the ξ↦Γ_ξ function; and φ(2,0,γ) enumerates the fixed points of all the ξ↦φ(1,ξ,0). Each instance of the generalized Veblen functions is continuous in the last nonzero variable (i.e., if one variable is made to vary and all later variables are kept constantly equal to zero).

The ordinal φ(1,0,0,0) is sometimes known as the Ackermann ordinal. The limit of the φ(1,0,…,0) where the number of zeroes ranges over ω, is sometimes known as the “small” Veblen ordinal.

Transfinitely many variables

More generally, Veblen 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 κ.

The definition can be given as follows: let α be a transfinite sequence of ordinals (i.e., an ordinal function with finite support) which ends in zero (i.e., such that α₀=0), and let α[0↦γ] denote the same function where the final 0 has been replaced by γ. Then γ↦φ(α[0↦γ]) is defined as the function enumerating the common fixed points of all functions ξ↦φ(β) where β ranges over all sequences which are obtained by decreasing the smallest-indexed nonzero value of α and replacing some smaller-indexed value with the indeterminate ξ (i.e., β=α[ι₀↦ζ,ι↦ξ] meaning that for the smallest index ι₀ such that α_ι₀ is nonzero the latter has been replaced by some value ζ<α_ι₀ and that for some smaller index ι<ι₀, the value α_ι=0 has been replaced with ξ).

For example, if α=(ω↦1) denotes the transfinite sequence with value 1 at ω and 0 everywhere else, then φ(ω↦1) is the smallest fixed point of all the functions ξ↦φ(ξ,0,…,0) with finitely many final zeroes (it is also the limit of the φ(1,0,…,0) with finitely many zeroes, the small Veblen ordinal).

The smallest ordinal α such that α is greater than φ applied to any function with support in α (i.e., which cannot be reached “from below” using the Veblen function of transfinitely many variables) is sometimes known as the “large” Veblen ordinal.

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, MR 1026933
• Schütte, Kurt (1977), Proof theory, Grundlehren der Mathematischen Wissenschaften, 225, Berlin-New York: Springer-Verlag, pp. xii+299, ISBN 3-540-07911-4, MR 0505313
• 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, MR 0882549
• 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