FANDOM


OswaldVeblen1915

Oswald Veblen, 1915

The Veblen functions are a hierarchy of normal functions \(\varphi_\alpha: On \rightarrow On\), proposed by american mathematician Oswald Veblen in his article "Continuous Increasing Functions of Finite and Transfinite Ordinals" in 1908.[1] This allows to obtain ordinals beyond limit of the Cantor normal form. The modern version of the Veblen function is described below.

The Veblen hierarchy Edit

The hierarchy is defined as follows:

1) \(\varphi_0(\gamma)=\omega^\gamma\),

2) for \(\alpha>0\), \(\varphi_\alpha(\gamma)=\) the \(1+\gamma\)th common 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\mapsto \omega^\xi\) and \(\zeta_\gamma\) enumerates the ordinals \(\xi\) such that \(\xi\mapsto \varepsilon_\xi\) ).

For example: \(\varphi_2(2)=\zeta_2\) is common fixed point of 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 common fixed point for this functions 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 Edit

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 Edit

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 \(\gamma\)th common 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 Edit

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 Edit

\(\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\),

\(\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\),

\(\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)\).

Transfinitary Veblen function Edit

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}\).

Comparison with theta function Edit

The extended Veblen function and Bird/Feferman theta-functions up to SVO are connected by the next 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)\).

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)\).

According to Hyp cos' estimation, 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 TREE(n) function.

The fast-growing hierarchy function indexed by the Large Veblen ordinal, \(f_{LVO}(10)\), is near to the lowest estimation of Bowers' meameamealokkapoowa oompa.

Sources Edit

  1. Veblen, Oswald. Continuous Increasing Functions of Finite and Transfinite Ordinals. Retrieved 2017-03-16.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.