FANDOM


ヴェブレン関数 (Veblen function; ヴェブレン関数; ヴェブレン階層; ファイ関数; φ関数) は、オズワルド・ヴェブレンが1908年の論文.[1] に書いた通常の関数 \(\varphi_\alpha: On \rightarrow On\) の階層である。この関数によってカントール標準形の限界を超える順序数を得ることができる。以下には、現代バージョンのヴェブレン関数を記す。

ヴェブレン階層

階層は以下のように定義される。

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

2) \(\alpha>0\) に対しては \(\varphi_\alpha(\gamma)\) は、すべての \(\beta<\alpha\) に共通の関数 \(\varphi_\beta(\xi)=\xi\) の0から数えて\(\gamma\) 番目の不動点

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

多変数(有限変数)に拡張されたヴェブレン関数

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:[2]

  • \(\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 en: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.

多変数ヴェブレン関数の極限順序数に対する基本列

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.

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

Γ関数

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

超限変数ヴェブレン関数

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 en:large Veblen ordinal (LVO):

  • \(LVO[0]=0\),
  • \(LVO[n+1]=\begin{pmatrix}1 \\ LVO[n] \end{pmatrix}\).

フェファーマンのθ関数との比較

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 en: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 en:fast-growing hierarchy function indexed by the en:Large Veblen ordinal, \(f_{LVO}(10)\), is near to the lowest estimation of Bowers' en:meameamealokkapoowa oompa.

出典

  1. Veblen, Oswald. Continuous Increasing Functions of Finite and Transfinite Ordinals. Retrieved 2017-03-16.
  2. Maksudov, Denis. Fundamental sequences for extended Veblen functionTraveling To The Infinity  Retrieved 2017-10-02.