Veblen function

In mathematics, the Veblen functions are a hierarchy of normal functions, introduced by Oswald Veblen in. 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.

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 then. From this and the fact that φ_β is strictly increasing we get the ordering: if and only if either or or.

Fundamental sequences for the Veblen hierarchy

The fundamental sequence for an ordinal with cofinality ω is a distinguished strictly increasing ω-sequence that 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 α,. 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 α.
A variation of Cantor normal form used in connection with the Veblen hierarchy is: every nonzero ordinal number α can be uniquely written as, where k > 0 is a natural number and each term after the first is less than or equal to the previous term, and each If a fundamental sequence can be provided for the last term, then that term can be replaced by such a sequence to get
For any β, if γ is a limit with then let
No such sequence can be provided for = ω⁰ = 1 because it does not have cofinality ω.
For we choose
For we use and i.e. 0,,, etc..
For, we use and
Now suppose that β is a limit:
If, then let
For, use
Otherwise, the ordinal cannot be described in terms of smaller ordinals using and this scheme does not apply to it.

The Γ function

The function Γ enumerates the ordinals α such that φ_α = α.
Γ₀ is the Feferman–Schütte ordinal, i.e. it is the smallest α such that φ_α = α.
For Γ₀, a fundamental sequence could be chosen to be and
For Γ_β+1, let and
For Γ_β where is a limit, let

Generalizations

Finitely many variables

To build the Veblen function of a finite number of arguments, let the binary function be as defined above.
Let be an empty string or a string consisting of one or more comma-separated zeros and be an empty string or a string consisting of one or more comma-separated ordinals with. The binary function can be written as where both and are empty strings.
The finitary Veblen functions are defined as follows:

if, then denotes the -th common fixed point of the functions for each

For example, is the -th fixed point of the functions, namely ; then enumerates the fixed points of that function, i.e., of the function; and enumerates the fixed points of all the. Each instance of the generalized Veblen functions is continuous in the last nonzero variable.
The ordinal is sometimes known as the Ackermann ordinal. The limit of the where the number of zeroes ranges over ω, is sometimes known as the "small" Veblen ordinal.
Every non-zero ordinal less than the small Veblen ordinal can be uniquely written in normal form for the finitary Veblen function:
where

is a positive integer
is a string consisting of one or more comma-separated ordinals where and each
Fundamental sequences for limit ordinals of finitary Veblen function

For limit ordinals, written in normal form for the finitary Veblen function:

,
,
and if and is a successor ordinal,
and if and are successor ordinals,
if is a limit ordinal,
if and is a limit ordinal,
if is a successor ordinal and is a limit 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 that ends in zero, and let α denote the same function where the final 0 has been replaced by γ. Then γ↦φ is defined as the function enumerating the common fixed points of all functions ξ↦φ where β ranges over all sequences that are obtained by decreasing the smallest-indexed nonzero value of α and replacing some smaller-indexed value with the indeterminate ξ.
For example, if α= denotes the transfinite sequence with value 1 at ω and 0 everywhere else, then φ is the smallest fixed point of all the functions ξ↦φ with finitely many final zeroes.
The smallest ordinal α such that α is greater than φ applied to any function with support in α is sometimes known as the "large" Veblen ordinal, or "great" Veblen number.

Simplified

Here is a simplified version of the transfinitary Veblen function:
We modify this to use functions from the class of all ordinals to itself as input. Such functions can be encoded by a set as follows:

the set is a finite set of ordered pairs of ordinals;
no ordinal appears more than once as the first member of such an ordered pair, i.e. the encoded function is single-valued;
the ordinal in the second position in an ordered pair is never zero, i.e. a value of zero is indicated by the absence of an ordered pair;
when using the set as a function, the input ordinal is compared to the first members of the ordered pairs, if it matches one, then the second member is returned as the value; otherwise the value is zero.

Using s and t for such sets and α, β, γ, and δ for ordinals, the definitions are:
Notations in this system begin with the zero-ary function 0, and use the binary function addition + to combine powers of ω which come from applying the transfinite Veblen function φ to these set-coded functions.
et cetera.
How many times can φ take on some value? The values are always powers of ω.
So powers of ω are always values of φ at least once. Epsilon numbers are fixed points of that, so they are always values at least twice.
Some ordinals are values of φ infinitely often. For example, Ω is a value an uncountable number of times.
So if D_φ < φ, then that is the last time that φ can take that value. So D_φ = φ is the norm for ordinals which are values more than once. D_φ > φ never occurs. But
and there are many other ordinals for which that is true. They are all very strong limits.
The preferred form of s to produce a value of φ is the one for which D_φ < φ. The ordering theorem is:
If α is an ordinal with no preferred form, then:
The ordering among epsilon numbers which do not have a preferred form depends on how those epsilon numbers are specified.

Further extensions

In, the Veblen function was extended further to a somewhat technical system known as dimensional Veblen. In this, one may take fixed points or row numbers, meaning expressions such as φ are valid, visualised as multi-dimensional arrays. It was proven that all ordinals below the Bachmann–Howard ordinal could be represented in this system, and that the representations for all ordinals below the large Veblen ordinal were aesthetically the same as in the original system.

Values

The function takes on several prominent values:

is the proof-theoretic ordinal of Peano arithmetic and the limit of what ordinals can be represented in terms of Cantor normal form and smaller ordinals.
, a bound on the order types of the recursive path orderings with finitely many function symbols, and the smallest ordinal closed under primitive recursive ordinal functions.
The Feferman–Schütte ordinal is equal to.
The small Veblen ordinal is equal to.