Veblen function

The Veblen functions are a hierarchy of normal functions \(\varphi_\alpha: \textrm{Ord} \rightarrow \textrm{Ord}\) on \(\textrm{Ord}\), proposed by American mathematician Oswald Veblen in his article "Continuous Increasing Functions of Finite and Transfinite Ordinals" in 1908. This allows obtaining ordinals beyond the limit of Cantor normal form. The modern version of the Veblen function is described below.
== The Veblen hierarchy ==
For a sophisticated formulation using derivation, see Derivative#Example. The hierarchy is defined as follows:
1) \(\varphi_0(\gamma)=\omega^\gamma\)
2) For \(\alpha>0\), \(\varphi_\alpha(\gamma)=\) the \(1+\gamma\)th common/simultaneous fixed point of the functions \(\varphi_\beta(\xi)=\xi\) for all \(\beta<\alpha\).
Thus \(\varphi_1(\gamma)=\varepsilon_\gamma\), \(\varphi_2(\gamma)=\zeta_\gamma\) and so on (\(\varepsilon_\gamma\) enumerates the ordinals \(\xi\) such that \(\xi = \omega^\xi\) and \(\zeta_\gamma\) enumerates the ordinals \(\xi\) such that \(\xi = \varepsilon_\xi\) ).
For example: \(\varphi_2(2)=\zeta_2\) is a fixed point of both the functions \(\varphi_0(\xi)=\xi\) and \(\varphi_1(\xi)=\xi\) so far as \(\zeta_2=\omega^{\zeta_2}\) as well as \(\zeta_2=\varepsilon_{\zeta_2}\) and this is third fixed point these functions have in common after \(\zeta_0\) and \(\zeta_1\).
Every non-zero ordinal \(\alpha<\Gamma_0\) can be uniquely written in normal form for the Veblen hierarchy:
\(\alpha=\varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k)\),
where
* \(\varphi_{\beta_1}(\gamma_1) \ge \varphi_{\beta_2}(\gamma_2) \ge \cdots \ge \varphi_{\beta_k}(\gamma_k)\)
* \(\gamma_m < \varphi_{\beta_m}(\gamma_m)\) for \(m \in \{1,...,k\}\)
Note: \(\Gamma_0\) is the smallest ordinal \(\alpha\) such that \(\varphi_\alpha(0)=\alpha\).
=== Fundamental sequences for the Veblen hierarchy ===
Fundamental sequence for a limit ordinal \(\alpha\) is a strictly increasing sequence which has the ordinal \(\alpha\) as its limit. Below \(\alpha[n]\) denotes the n-th element of the fundamental sequence assigned to the limit ordinal \(\alpha\), where \(n\) is a non-negative integer.
Fundamental sequences for the Veblen's hierarchy are defined as follows:
For limit ordinals \(\alpha<\Gamma_0\), written in normal form for the Veblen hierarchy
1.1) \((\varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k))[n]=\varphi_{\beta_1}(\gamma_1) + \cdots + \varphi_{\beta_{k-1}}(\gamma_{k-1}) + \varphi_{\beta_k}(\gamma_k) [n]\),
1.2) \(\varphi_0(\gamma)=\omega^{\gamma}\) and \(\varphi_0(\gamma+1) [n] = \omega^{\gamma} \cdot n\),
1.3) \(\varphi_{\beta+1}(0)[n]=\varphi_{\beta}^n(0)\),
1.4) \(\varphi_{\beta+1}(\gamma+1)[n]=\varphi_{\beta}^n(\varphi_{\beta+1}(\gamma)+1)\),
1.5) \(\varphi_{\beta}(\gamma) [n] = \varphi_{\beta}(\gamma [n])\) for a limit ordinal \(\gamma<\varphi_\beta(\gamma)\),
1.6) \(\varphi_{\beta}(0) [n] = \varphi_{\beta [n]}(0)\) for a limit ordinal \(\beta<\varphi_\beta(0)\),
1.7) \(\varphi_{\beta}(\gamma+1) [n] = \varphi_{\beta [n]}(\varphi_{\beta}(\gamma)+1)\) for a limit ordinal \(\beta\).
In rules 1.3 and 1.4, \(\varphi^n\) denotes function iteration: \(\varphi_{\beta}^0(\gamma)=\gamma\) and \(\varphi_{\beta}^{m+1}(\gamma)=\varphi_{\beta}(\varphi_{\beta}^{m}(\gamma))\).
== The extended (finitary) Veblen function ==
For the building of Veblen function with arbitrary amount of arguments, let's consider \(\varphi_\alpha(\gamma)\) as binary function \(\varphi(\alpha, \gamma)\).
Let z be an empty string or a string with one or more zeros \(0,0,...,0\) and s be an empty string or an arbitrary string of ordinal variables \(\alpha_1, \alpha_2,...,\alpha_n\) with \(\alpha_1>0\). The binary function \(\varphi(\alpha, \gamma)\) can be written as \(\varphi(s,\alpha, z,\gamma)\) where both s and z are empty strings.
The extended Veblen functions are defined as follows:
*\(\varphi(\gamma)=\omega^\gamma\),
*\(\varphi(z,s,\gamma)=\varphi(s,\gamma)\),
* if \(\alpha_{n+1}>0\), where \(n\geq 0\), then \(\varphi(s,\alpha_{n+1}, z, \gamma)\) denotes the \(1+\gamma\)th common/simultaneous fixed point of the functions \(\xi \mapsto \varphi(s, \beta, \xi,z)\) for each \(\beta<\alpha_{n+1}\).
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
*\(\varphi(s_1)\geq\varphi(s_2)\geq\cdots\geq\varphi(s_k)\),
*\(s_m\) is an arbitrary string of ordinal variables \(\alpha_{m,1}, \alpha_{m,2},...,\alpha_{m,n_m}\) where \(m \in \{1,...,k\}\)
* \(\alpha_{m,1}>0\) and \(\alpha_{m,i} <\varphi(s_m)\) for \(m \in \{1,...,k\}\) and \(i \in \{1,..,n_m\}\),
* \(k, n_1,...,n_k\) are positive integers.
=== Fundamental sequences for limit ordinals of finitary Veblen function ===
For limit ordinals \(\alpha<SVO\), written in normal form for the finitary Veblen function
2.1) \((\varphi(s_1)+\varphi(s_2)+\cdots+\varphi(s_k))[n]=\varphi(s_1)+\varphi(s_2)+\cdots+\varphi(s_k)[n]\),
2.2) \(\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.
\),
2.3) \(\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,
2.4) \(\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,
2.5) \(\varphi(s,\beta,z,\gamma)[n]=\varphi(s,\beta,z,\gamma[n])\) if \(\gamma\) is a limit ordinal,
2.6) \(\varphi(s,\beta,z,\gamma)[n]=\varphi(s,\beta[n],z,\gamma)\) if \(\gamma=0\) and \(\beta\) is a limit ordinal,
2.7) \(\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.
=== Examples ===
\(\varphi(1,0)[n]=\underbrace{\varphi(0, \varphi (0, ... \varphi}_{n \quad \varphi's}(0,0)...))=\underbrace{\varphi(\varphi(...\varphi}_{n \quad \varphi's}(0)...))=\varepsilon_0[n]\),
\(\varphi(1,0,0)[n]=\underbrace{\varphi(0, \varphi (0, ... \varphi}_{n \quad \varphi's}(0,0,0)...,0),0)=\underbrace{\varphi( \varphi ( ... \varphi}_{n \quad \varphi's}(0,0)...,0),0)=\Gamma_0[n]\),
\(\varphi(1,1,1,0,0,0)[n]=\underbrace{\varphi(1,1,0,\varphi(1,1,0 ... \varphi}_{n \quad \varphi's}(1,1,0,0,0,0)...,0,0),0,0)\).
=== Gamma-function ===
Gamma-function is the function enumerates the ordinals \(\alpha\) such that \(\varphi(\alpha,0)=\alpha\) or in other words \(\Gamma_\beta=\varphi(1,0,\beta)=\)the \((1+\beta)\)-th ordinal in the set \(\{\gamma|\varphi(\gamma,0)=\gamma\}\). Same way we assign \(\Gamma_\beta[n]=\varphi(1,0,\beta)[n]\).
== Transfinitary Veblen function ==
For definition of fundamental sequences of Veblen function with ordinal number of variables it is possible to use Schutte Klammersymbolen in form of two-row matrix where a k-th ordinal of second row \(\beta_k \geq 0\) defines position of a k-th ordinal of the first row \(\alpha_k>0\) in string of arguments of the Veblen function.
For example: \(\begin{pmatrix}\alpha_1 & \alpha_2 & \alpha_3 \\8 & 5 & 0 \end{pmatrix}=\varphi(\alpha_1,0,0,\alpha_2,0,0,0,0,\alpha_3)\).
If a limit ordinal \(\alpha\) is written in next normal form
\(\begin{pmatrix} \alpha_{1,1} & \cdots &\alpha_{1,n_1} \\ \beta_{1,1} & \cdots & \beta_{1,n_1} \end{pmatrix}+\begin{pmatrix} \alpha_{2,1} & \cdots &\alpha_{2,n_2} \\ \beta_{2,1} & \cdots & \beta_{2,n_2} \end{pmatrix}+\cdots+\begin{pmatrix} \alpha_{k,1} & \cdots &\alpha_{k,n_k} \\ \beta_{k,1} & \cdots & \beta_{k,n_k} \end{pmatrix}\),
where
*\(\begin{pmatrix} \alpha_{1,1} & \cdots &\alpha_{1,n_1} \\ \beta_{1,1} & \cdots & \beta_{1,n_1} \end{pmatrix} \geq \begin{pmatrix} \alpha_{2,1} & \cdots &\alpha_{2,n_2} \\ \beta_{2,1} & \cdots & \beta_{2,n_2} \end{pmatrix} \geq \cdots \geq \begin{pmatrix} \alpha_{k,1} & \cdots &\alpha_{k,n_k} \\ \beta_{k,1} & \cdots & \beta_{k,n_k} \end{pmatrix}\),
*\(\alpha_{m,i}<\begin{pmatrix} \alpha_{m,1} & \cdots &\alpha_{m,n_m} \\ \beta_{m,1} & \cdots & \beta_{m,n_m} \end{pmatrix}\) for all \(i \in \{1,...,n_m\}\), \(m \in \{1,...,k\}\),
*\(\beta_{m,i}<\begin{pmatrix} \alpha_{m,1} & \cdots &\alpha_{m,n_m} \\ \beta_{m,1} & \cdots & \beta_{m,n_m} \end{pmatrix}\) for all \(i \in \{1,...,n_m\}\), \(m \in \{1,...,k\}\),
*\(\begin{pmatrix} \alpha_{k,1} & \cdots &\alpha_{k,n_k} \\ \beta_{k,1} & \cdots & \beta_{k,n_k} \end{pmatrix}\) is a limit ordinal,
*\(k,n_1,...,n_k\) are positive integers,
then
\(\alpha[n]=\begin{pmatrix} \alpha_{1,1} & \cdots &\alpha_{1,n_1} \\ \beta_{1,1} & \cdots & \beta_{1,n_1} \end{pmatrix}+\begin{pmatrix} \alpha_{2,1} & \cdots &\alpha_{2,n_2} \\ \beta_{2,1} & \cdots & \beta_{2,n_2} \end{pmatrix}+\cdots+\begin{pmatrix} \alpha_{k,1} & \cdots &\alpha_{k,n_k} \\ \beta_{k,1} & \cdots & \beta_{k,n_k} \end{pmatrix}[n]\) (2).
If \(n_k=1\) and \(\beta_{k,n_k}=0\) then the last term (LT) in expression (2) is equal to \(\begin{pmatrix}\alpha_{k,1} \\ 0 \end{pmatrix}=\varphi(\alpha_{k,1})=\omega^{\alpha_{k,1}}\) and should use rule for single-argument form to assign fundamental sequences (FS) for LT, otherwise use rules 3.1-3.9 to assign FS for LT:
3.1) \(\begin{pmatrix}\cdots & \alpha+1 \\ \cdots & \beta+1 \end{pmatrix}[0]=0\)
and \(\begin{pmatrix}\cdots & \alpha+1 \\ \cdots & \beta+1 \end{pmatrix}[n+1]=\begin{pmatrix}\cdots & \alpha & \begin{pmatrix}\cdots & \alpha+1 \\ \cdots & \beta+1 \end{pmatrix}[n] \\ \cdots & \beta+1 & \beta \end{pmatrix}\),
3.2) \(\begin{pmatrix}\cdots & \alpha+1 & \gamma+1 \\ \cdots & \beta+1 & 0 \end{pmatrix}[0]=\begin{pmatrix}\cdots & \alpha+1 & \gamma \\ \cdots & \beta+1 & 0 \end{pmatrix}+1\)
and \(\begin{pmatrix}\cdots & \alpha+1 & \gamma+1 \\ \cdots & \beta+1 & 0 \end{pmatrix}[n+1]=\begin{pmatrix}\cdots & \alpha & \begin{pmatrix}\cdots & \alpha+1 & \gamma+1 \\ \cdots & \beta+1 & 0 \end{pmatrix}[n] \\ \cdots & \beta+1 & \beta \end{pmatrix}\),
3.3) \(\begin{pmatrix}\cdots & \alpha & \gamma \\ \cdots & \beta & 0 \end{pmatrix}[n]=\begin{pmatrix}\cdots & \alpha & \gamma [n] \\ \cdots & \beta & 0 \end{pmatrix}\) if \(\gamma\) is a limit ordinal,
3.4) \(\begin{pmatrix}\cdots & \alpha & \\ \cdots & \beta+1 \end{pmatrix}[n]=\begin{pmatrix}\cdots & \alpha [n] & \\ \cdots & \beta+1 \end{pmatrix}\) if \(\alpha\) is a limit ordinal,
3.5) \(\begin{pmatrix}\cdots & \alpha & \gamma+1 \\ \cdots & \beta+1 & 0 \end{pmatrix}[n]=\begin{pmatrix}\cdots & \alpha [n] & \begin{pmatrix}\cdots & \alpha & \gamma \\ \cdots & \beta+1 & 0 \end{pmatrix}+1 \\ \cdots & \beta+1 & \beta \end{pmatrix}\) if \(\alpha\) is a limit ordinal,
3.6) \(\begin{pmatrix}\cdots & \alpha+1\\ \cdots & \beta\end{pmatrix}[n]=\begin{pmatrix}\cdots & \alpha & 1 \\ \cdots & \beta& \beta [n]\end{pmatrix}\) if \(\beta\) is a limit ordinal,
3.7) \(\begin{pmatrix}\cdots & \alpha+1 & \gamma+1 \\ \cdots & \beta & 0 \end{pmatrix}[n]=\begin{pmatrix}\cdots & \alpha & \begin{pmatrix}\cdots & \alpha+1 & \gamma \\ \cdots & \beta & 0 \end{pmatrix}+1 \\ \cdots & \beta & \beta[n] \end{pmatrix}\) if \(\beta\) is a limit ordinal,
3.8) \(\begin{pmatrix}\cdots & \alpha\\ \cdots & \beta\end{pmatrix}[n]=\begin{pmatrix}\cdots & \alpha [n] \\ \cdots & \beta \end{pmatrix}\) if \(\alpha\) and \(\beta\) are limit ordinals,
3.9) \(\begin{pmatrix}\cdots & \alpha & \gamma+1 \\ \cdots & \beta & 0 \end{pmatrix}[n]=\begin{pmatrix}\cdots & \alpha [n]& \begin{pmatrix}\cdots & \alpha & \gamma \\ \cdots & \beta & 0 \end{pmatrix}+1 \\ \cdots & \beta & \beta [n] \end{pmatrix}\) if \(\alpha\) and \(\beta\) are limit ordinals.
The limit of this notation is large Veblen ordinal (LVO):
*\(LVO[0]=0\),
*\(LVO[n+1]=\begin{pmatrix}1 \\ LVO[n] \end{pmatrix}\).
The LVO also has an informal visualization: \(\begin{pmatrix}1 \\ \begin{pmatrix}1 \\ \begin{pmatrix}1 \\ \begin{pmatrix}1 \\ ... \end{pmatrix} \end{pmatrix} \end{pmatrix} \end{pmatrix}\)
=== Comparison with theta functions ===
The extended Veblen function and Bird's theta function up to SVO are connected by this expression:
\(\theta(\Omega^{n - 1}\alpha_{1} + \cdots + \Omega^2\alpha_{n-2} + \Omega \alpha_{n-1} + \alpha_n, \gamma) = \varphi(\alpha_{1}, \ldots, \alpha_{n-2}, \alpha_{n-1}, \alpha_n, \gamma)\)
and \(\theta(\alpha, 0)\) can be abbreviated as \(\theta(\alpha)\). In this terms \(SVO=\theta(\Omega^\omega)\).
The extended Veblen function and Feferman's theta function up to SVO are connected by this expression:
\(\theta_{\Omega^{n-1}\alpha_1+\cdots+\Omega^2\alpha_{n-2}+\Omega\alpha_{n-1}+\alpha_n}(\gamma)=\varphi(\alpha_{1}, \ldots, \alpha_{n-2}, \alpha_{n-1}, \alpha_n, \gamma)\)
For transfinary Veblen function for example:
\(\begin{pmatrix} 1\\ \varphi(\alpha_{1}, \ldots, \alpha_{n-2}, \alpha_{n-1}, \alpha_n, \gamma)\end{pmatrix}=\theta(\Omega^{\theta(\Omega^{n - 1}\alpha_{1} + \cdots + \Omega^2\alpha_{n-2} + \Omega \alpha_{n-1} + \alpha_n, \gamma)})\),
\(\begin{pmatrix} 1\\\begin{pmatrix} 1\\ \varphi(\alpha_{1}, \ldots, \alpha_{n-2}, \alpha_{n-1}, \alpha_n, \gamma)\end{pmatrix}\end{pmatrix}=\theta(\Omega^{\theta(\Omega^{\theta(\Omega^{n - 1}\alpha_{1} + \cdots + \Omega^2\alpha_{n-2} + \Omega \alpha_{n-1} + \alpha_n, \gamma)})})\)
and so on. In this terms \(LVO=\theta(\Omega^\Omega)\).
== Issues on Analysis ==
This community believed Hyp cos' estimation that the growth rate of the function of fast-growing hierarchy \(f_{\begin{pmatrix}\omega \\ \omega \end{pmatrix}}(n) \) is less than or equal to the growth rate of Harvey Friedman's \(\textrm{TREE}[n]\) function, but there is no actual proof of the estimation. See also related issues on analysis of \(\textrm{TREE}[n]\) function.
Also, this community believed that the fast-growing hierarchy function indexed by the Large Veblen ordinal, \(f_{LVO}(10)\), with respect to the standard system of fundamental sequences is near to the lowest estimation of Bowers' meameamealokkapoowa oompa, but it is well-known that the number is ill-defined, while \(f_{LVO}(10)\) is well-defined.
In this way, well-known results in this community are not necessarily based on proofs, and hence might be wrong or even meaningless as the latter example shows.
Another important property of the Veblen function that affects analysis is how the last entry isn't necessarily preserved when taking suprema. For example, \(\textrm{sup}\{\varphi_n(\varphi_\omega(0)+1):n\in\mathbb N\}\) is not \(\varphi_\omega(\varphi_\omega(0)+1)\), but instead \(\varphi_\omega(1)\).
== Sources ==
== See also ==
ja:ヴェブレン関数
zh:凡勃倫函數
ru:Функция Веблена
Category:Functions
Category:Transfinite ordinals