Veblen function

From Wikipedia, the free encyclopedia

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

Contents

[edit] The Veblen hierarchy

In the special case when φ0(α)=ωα this family of functions is known as the Veblen hierarchy. The function φ1 is the same as the ε function: φ1(α)= εα. Ordering: \varphi_\alpha(\beta) < \varphi_\gamma(\delta) if and only if either (α = γ and β < δ) or (α < γ and \beta < \varphi_\gamma(\delta)) or (α > γ and \varphi_\alpha(\beta) < \delta).

[edit] Fundamental sequences for the Veblen hierarchy

The fundamental sequence of 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.

A variation of Cantor normal form used in connection with the Veblen hierarchy is -- every ordinal number α can be uniquely written as \varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k), where k is a natural number and each term after the first is less than or equal to the previous term and each γj is not a fixed point of \varphi_{\beta_j}. If a fundamental sequence can be provided for the last term, then that term can be replaced by such a sequence to get a fundamental sequence for α.

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

For \varphi_0(\gamma+1) = \omega ^{\gamma+1} = \omega^ \gamma \cdot \omega, we choose the function which maps the natural number m to \omega^\gamma \cdot m.

If γ is a limit which is not a fixed point of \varphi_0, then for \varphi_0(\gamma), we replace γ by its fundamental sequence inside \varphi_0.

For \varphi_{\beta+1}(0), we use 0, \varphi_{\beta}(0), \varphi_{\beta}(\varphi_{\beta}(0)), \varphi_{\beta}(\varphi_{\beta}(\varphi_{\beta}(0))), etc..

For \varphi_{\beta+1}(\gamma+1), we use \varphi_{\beta+1}(\gamma)+1, \varphi_{\beta}(\varphi_{\beta+1}(\gamma)+1), \varphi_{\beta}(\varphi_{\beta}(\varphi_{\beta+1}(\gamma)+1)), etc..

If γ is a limit which is not a fixed point of \varphi_{\beta+1}, then for \varphi_{\beta+1}(\gamma), we replace γ by its fundamental sequence inside \varphi_{\beta+1}.

Now suppose that β is a limit: If \beta < \varphi_{\beta}(0), then for \varphi_{\beta}(0), we replace β by its fundamental sequence.

For \varphi_{\beta}(\gamma+1), use \varphi_{\beta_m}(\varphi_{\beta}(\gamma)+1) where βm is the fundamental sequence for β.

If γ is a limit which is not a fixed point of \varphi_{\beta}, then for \varphi_{\beta}(\gamma), we replace γ by its fundamental sequence inside \varphi_{\beta}.

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

[edit] The Γ function

The function Γ enumerates the ordinals α such that φα(0) = α. Γ0 is the Feferman-Schutte ordinal, i.e. it is the smallest α such that φα(0) = α.

[edit] 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, ...,α0) 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.

[edit] References