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.

1 The Veblen hierarchy
- 1.1 Fundamental sequences for the Veblen hierarchy
- 1.2 The Γ function
2 Generalizations
3 References

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) %2B \varphi_{\beta_2}(\gamma_2) %2B \cdots %2B \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%2B1}}(\gamma_{m%2B1}) \,,$ 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) %2B \cdots %2B \varphi_{\beta_{k-1}}(\gamma_{k-1}) %2B (\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%2B1) = \omega ^{\gamma%2B1} = \omega^ \gamma \cdot \omega \,,$ we choose $\varphi_0(\gamma%2B1) [n] = \varphi_0(\gamma) \cdot n = \omega^{\gamma} \cdot n \,.$

For $\varphi_{\beta%2B1}(0) \,,$ we use $\varphi_{\beta%2B1}(0) [0] = 0 \,$ and $\varphi_{\beta%2B1}(0) [n%2B1] = \varphi_{\beta}(\varphi_{\beta%2B1}(0) [n]) \,,$ i.e. 0, $\varphi_{\beta}(0)$ , $\varphi_{\beta}(\varphi_{\beta}(0))$ , etc..

For $\varphi_{\beta%2B1}(\gamma%2B1)$ , we use $\varphi_{\beta%2B1}(\gamma%2B1) [0] = \varphi_{\beta%2B1}(\gamma)%2B1 \,$ and $\varphi_{\beta%2B1}(\gamma%2B1) [n%2B1] = \varphi_{\beta} (\varphi_{\beta%2B1}(\gamma%2B1) [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%2B1)$ , use $\varphi_{\beta}(\gamma%2B1) [n] = \varphi_{\beta [n]}(\varphi_{\beta}(\gamma)%2B1) \,.$

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%2B1] = \varphi_{\Gamma_0 [n]} (0) \,.$

For Γ_β+1, let $\Gamma_{\beta%2B1} [0] = \Gamma_{\beta} %2B 1 \,$ and $\Gamma_{\beta%2B1} [n%2B1] = \varphi_{\Gamma_{\beta%2B1} [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, 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