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.

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})+\varphi _{\beta _{2}}(\gamma _{2})+\cdots +\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+1}}(\gamma _{m+1})\,,$ 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})+\cdots +\varphi _{\beta _{k-1}}(\gamma _{k-1})+(\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 +1)=\omega ^{\gamma +1}=\omega ^{\gamma }\cdot \omega \,,$ we choose $\varphi _{0}(\gamma +1)[n]=\varphi _{0}(\gamma )\cdot n=\omega ^{\gamma }\cdot n\,.$

For $\varphi _{\beta +1}(0)\,,$ we use $\varphi _{\beta +1}(0)[0]=0$ and $\varphi _{\beta +1}(0)[n+1]=\varphi _{\beta }(\varphi _{\beta +1}(0)[n])\,,$ i.e. 0, $\varphi _{\beta }(0)$, $\varphi _{\beta }(\varphi _{\beta }(0))$, etc..

For $\varphi _{\beta +1}(\gamma +1)$, we use $\varphi _{\beta +1}(\gamma +1)[0]=\varphi _{\beta +1}(\gamma )+1$ and $\varphi _{\beta +1}(\gamma +1)[n+1]=\varphi _{\beta }(\varphi _{\beta +1}(\gamma +1)[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 +1)$, use $\varphi _{\beta }(\gamma +1)[n]=\varphi _{\beta [n]}(\varphi _{\beta }(\gamma )+1)\,.$

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+1]=\varphi _{\Gamma _{0}[n]}(0)\,.$

For Γがんま_{βべーた+1}, let $\Gamma _{\beta +1}[0]=\Gamma _{\beta }+1$ and $\Gamma _{\beta +1}[n+1]=\varphi _{\Gamma _{\beta +1}[n]}(0)\,.$

For Γがんま_βべーた where $\beta <\Gamma _{\beta }$ is a limit, let $\Gamma _{\beta }[n]=\Gamma _{\beta [n]}\,.$

Generalizations

Finitely many variables

To build the Veblen function of a finite number of arguments (finitary Veblen function), let the binary function $\varphi (\alpha ,\gamma )$ be $\varphi _{\alpha }(\gamma )$ as defined above.

Let $z$ be an empty string or a string consisting of one or more comma-separated zeros $0,0,...,0$ and $s$ be an empty string or a string consisting of one or more comma-separated ordinals $\alpha _{1},\alpha _{2},...,\alpha _{n}$ with $\alpha _{1}>0$. The binary function $\varphi (\beta ,\gamma )$ can be written as $\varphi (s,\beta ,z,\gamma )$ where both $s$ and $z$ are empty strings. The finitary Veblen functions are defined as follows:

• $\varphi (\gamma )=\omega ^{\gamma }$
• $\varphi (z,s,\gamma )=\varphi (s,\gamma )$
• if $\beta >0$, then $\varphi (s,\beta ,z,\gamma )$ denotes the $(1+\gamma )$-th common fixed point of the functions $\xi \mapsto \varphi (s,\delta ,\xi ,z)$ for each $\delta <\beta$

For example, $\varphi (1,0,\gamma )$ is the $(1+\gamma )$-th fixed point of the functions $\xi \mapsto \varphi (\xi ,0)$, namely $\Gamma _{\gamma }$; then $\varphi (1,1,\gamma )$ enumerates the fixed points of that function, i.e., of the $\xi \mapsto \Gamma _{\xi }$ function; and $\varphi (2,0,\gamma )$ enumerates the fixed points of all the $\xi \mapsto \varphi (1,\xi ,0)$. Each instance of the generalized Veblen functions is continuous in the last nonzero variable (i.e., if one variable is made to vary and all later variables are kept constantly equal to zero).

The ordinal $\varphi (1,0,0,0)$ is sometimes known as the Ackermann ordinal. The limit of the $\varphi (1,0,...,0)$ where the number of zeroes ranges over ωおめが, is sometimes known as the "small" Veblen ordinal.

Every non-zero ordinal $\alpha$ less than the small Veblen ordinal (SVO) can be uniquely written in normal form for the finitary Veblen function:

$\alpha =\varphi (s_{1})+\varphi (s_{2})+\cdots +\varphi (s_{k})$

where

• $k$ is a positive integer
• $\varphi (s_{1})\geq \varphi (s_{2})\geq \cdots \geq \varphi (s_{k})$
• $s_{m}$ is a string consisting of one or more comma-separated ordinals $\alpha _{m,1},\alpha _{m,2},...,\alpha _{m,n_{m}}$ where $\alpha _{m,1}>0$ and each $\alpha _{m,i}<\varphi (s_{m})$

Fundamental sequences for limit ordinals of finitary Veblen function

For limit ordinals $\alpha <SVO$, written in normal form for the finitary Veblen function:

• $(\varphi (s_{1})+\varphi (s_{2})+\cdots +\varphi (s_{k}))[n]=\varphi (s_{1})+\varphi (s_{2})+\cdots +\varphi (s_{k})[n]$,
• $\varphi (\gamma )[n]=\left\{{\begin{array}{lcr}n\quad {\text{if}}\quad \gamma =1\\\varphi (\gamma -1)\cdot n\quad {\text{if}}\quad \gamma \quad {\text{is a successor ordinal}}\\\varphi (\gamma [n])\quad {\text{if}}\quad \gamma \quad {\text{is a limit ordinal}}\\\end{array}}\right.$,
• $\varphi (s,\beta ,z,\gamma )[0]=0$ and $\varphi (s,\beta ,z,\gamma )[n+1]=\varphi (s,\beta -1,\varphi (s,\beta ,z,\gamma )[n],z)$ if $\gamma =0$ and $\beta$ is a successor ordinal,
• $\varphi (s,\beta ,z,\gamma )[0]=\varphi (s,\beta ,z,\gamma -1)+1$ and $\varphi (s,\beta ,z,\gamma )[n+1]=\varphi (s,\beta -1,\varphi (s,\beta ,z,\gamma )[n],z)$ if $\gamma$ and $\beta$ are successor ordinals,
• $\varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta ,z,\gamma [n])$ if $\gamma$ is a limit ordinal,
• $\varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta [n],z,\gamma )$ if $\gamma =0$ and $\beta$ is a limit ordinal,
• $\varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta [n],\varphi (s,\beta ,z,\gamma -1)+1,z)$ if $\gamma$ is a successor ordinal and $\beta$ 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 κかっぱ^κかっぱ (ordinal exponentiation). So one is defining a function φふぁい from κかっぱ^κかっぱ into κかっぱ.

The definition can be given as follows: let αあるふぁ be a transfinite sequence of ordinals (i.e., an ordinal function with finite support) which ends in zero (i.e., such that αあるふぁ₀=0), and let αあるふぁ[γがんま@0] denote the same function where the final 0 has been replaced by γがんま. Then γがんま↦φふぁい(αあるふぁ[γがんま@0]) is defined as the function enumerating the common fixed points of all functions ξくしー↦φふぁい(βべーた) where βべーた ranges over all sequences which are obtained by decreasing the smallest-indexed nonzero value of αあるふぁ and replacing some smaller-indexed value with the indeterminate ξくしー (i.e., βべーた=αあるふぁ[ζぜーた@ιいおた₀,ξくしー@ιいおた] meaning that for the smallest index ιいおた₀ such that αあるふぁ_ιいおた0 is nonzero the latter has been replaced by some value ζぜーた<αあるふぁ_ιいおた0 and that for some smaller index ιいおた<ιいおた₀, the value αあるふぁ_ιいおた=0 has been replaced with ξくしー).

For example, if αあるふぁ=(1@ωおめが) denotes the transfinite sequence with value 1 at ωおめが and 0 everywhere else, then φふぁい(1@ωおめが) is the smallest fixed point of all the functions ξくしー↦φふぁい(ξくしー,0,...,0) with finitely many final zeroes (it is also the limit of the φふぁい(1,0,...,0) with finitely many zeroes, the small Veblen ordinal).

The smallest ordinal αあるふぁ such that αあるふぁ is greater than φふぁい applied to any function with support in αあるふぁ (i.e., which cannot be reached "from below" using the Veblen function of transfinitely many variables) is sometimes known as the "large" Veblen ordinal, or "great" Veblen number.

Further extensions

In Massmann & Kwon (2023), 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 φふぁい(1@(1,0)) are valid (representing the large Veblen ordinal), 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:

• $\varphi (1,0)=\varepsilon _{0}$ 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.
• $\varphi (\omega ,0)$, 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-Schutte ordinal $\Gamma _{0}$ is equal to $\varphi (1,0,0)$.
• The small Veblen ordinal is equal to $\varphi {\begin{pmatrix}1\\\omega \end{pmatrix}}$.

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, vol. 1407, Berlin: Springer-Verlag, doi:10.1007/978-3-540-46825-7, ISBN 978-3-540-51842-6, MR 1026933
• Schütte, Kurt (1977), Proof theory, Grundlehren der Mathematischen Wissenschaften, vol. 225, Berlin-New York: Springer-Verlag, pp. xii+299, ISBN 978-3-540-07911-8, MR 0505313
• Takeuti, Gaisi (1987), Proof theory, Studies in Logic and the Foundations of Mathematics, vol. 81 (Second ed.), Amsterdam: North-Holland Publishing Co., ISBN 978-0-444-87943-1, 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
• Massmann, Jayde Sylvie; Kwon, Adrian Wang (October 20, 2023), Extending the Veblen Function, arXiv:2310.12832{{citation}}: CS1 maint: date and year (link)