strictly increasing function

Veblen function

In mathematics, the Veblen functions are a hierarchy of functions from ordinals to ordinals, introduced by . 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 functions (i.e. normal functions) from ordinals to ordinals.

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 (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 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 gamma_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 beta_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.

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) = α.


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.


|series= Lecture Notes in Mathematics|volume= 1407|publisher= Springer-Verlag|place= Berlin|year= 1989|ISBN= 3-540-51842-8 }}

  • Smorynski, C. The varieties of arboreal experience Math. Intelligencer 4 (1982), no. 4, 182-189; contains an informal description of the Veblen hierarchy.
  • Larry W. Miller, Normal Functions and Constructive Ordinal Notations,The Journal of Symbolic Logic,volume 41,number 2,June 1976,pages 439 to 459.
Search another word or see strictly increasing functionon Dictionary | Thesaurus |Spanish
Copyright © 2014, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature