Definitions

# 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\left(beta\right) < varphi_gamma\left(delta\right)$ if and only if either ($alpha = gamma$ and $beta < delta$) or ($alpha < gamma$ and $beta < varphi_gamma\left(delta\right)$) or ($alpha > gamma$ and $varphi_alpha\left(beta\right) < 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_\left\{beta_1\right\}\left(gamma_1\right) + varphi_\left\{beta_2\right\}\left(gamma_2\right) + cdots + varphi_\left\{beta_k\right\}\left(gamma_k\right)$, 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_\left\{beta_j\right\}$. 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\left(0\right)$ = ω0 = 1 because it does not have cofinality ω.

For $varphi_0\left(gamma+1\right) = omega ^\left\{gamma+1\right\} = 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\left(gamma\right)$, we replace γ by its fundamental sequence inside $varphi_0$.

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

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

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

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

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

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

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

## 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.

## References

• Hilbert Levitz, , expository article (8 pages, in PostScript)

|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