Veblen 函数

Veblen函数（别名：$\phi$ 函数）是一个 $\mathrm{O}\mathrm{r}\mathrm{d}\mathrm{\to }\mathrm{O}\mathrm{r}\mathrm{d}$ 的序数函数，由美国数学家 Oswald Veblen 定义。

定义

二元 Veblen 函数

Veblen 函数的定义基于序数函数的不动点。

二元 Veblen 函数$\phi (\alpha ,\beta )(\alpha ,\beta \in \mathrm{O}\mathrm{r}\mathrm{d})$的定义如下：

1. $\phi (0,\beta )=\phi (\beta )={\omega }^{\beta }$
2. $\phi (\alpha +1,\beta )$ 是函数 $x\mapsto \phi (\alpha ,x)$的第 $1+\beta$ 个不动点。
3. 对于极限序数 $\alpha$,$\phi (\alpha ,\beta )$ 为所有 $x\mapsto \phi (\gamma ,x)(\gamma <\alpha )$ 的第 $1+\beta$ 个公共不动点。

Veblen 函数作为一个序数记号，其合法表达式可按以下方式递归定义：

1. 0是合法表达式；
2. 若$\alpha ,\beta$是合法表达式，则$\alpha +\beta$也是合法表达式；
3. 若$\alpha ,\beta$是合法表达式，则$\phi (\alpha ,\beta )$也是合法表达式。

其基本列定义如下：

1. $(\phi ({\alpha }_1,{\beta }_1)+\phi ({\alpha }_2,{\beta }_2)+\cdots +\phi ({\alpha }_k,{\beta }_k))[n]=\phi ({\alpha }_1,{\beta }_1)+\phi ({\alpha }_2,{\beta }_2)+\cdots +\phi ({\alpha }_k,{\beta }_k)[n]$
2. $\phi (0,0)=1$
3. $\phi (0,\beta +1)[n]=\phi (0,\beta )\cdot n$
4. 对于极限序数 $\beta$,$\phi (\alpha ,\beta )[n]=\phi (\alpha ,\beta [n])$
5. $\phi (\alpha +1,0)[0]=0$
6. $\phi (\alpha +1,0)[n+1]=\phi (\alpha ,\phi (\alpha +1,0)[n])$
7. $\phi (\alpha +1,\beta +1)[0]=\phi (\alpha +1,\beta )+1$
8. $\phi (\alpha +1,\beta +1)[n+1]=\phi (\alpha ,\phi (\alpha +1,\beta +1)[n])$
9. 对于极限序数 $\alpha$,$\phi (\alpha ,0)[n]=\phi (\alpha [n],0)$
10. 对于极限序数 $\alpha$,$\phi (\alpha ,\beta +1)[n]=\phi (\alpha [n],\phi (\alpha ,\beta )+1)$

有限元 Veblen 函数

约定

我们使用一些缩写："#"表示任意序列，"Z"表示由若干个0构成序列，这两个记号均可以表示空序列。

对于表达式$\phi ({\alpha }_n,{\alpha }_{n-1},\cdots ,{\alpha }_1,\beta )$，记$k$为使${\alpha }_k\ne 0$的最小正整数，令$\mathrm{\#}={\alpha }_n,\cdots ,{\alpha }_{k+1}$,$Z={\alpha }_{k-1},\cdots ,{\alpha }_1$，则该表达式可记为$\phi (\mathrm{\#},{\alpha }_k,Z,\beta )$。

规则

有限元 Veblen 函数的基本列定义如下：

1. $\phi (Z,\mathrm{\#})=\phi (\mathrm{\#})$
2. $\phi (\mathrm{\#},\alpha +1,Z,0)[0]=0$
3. $\phi (\mathrm{\#},\alpha +1,Z,0)[n+1]=\phi (\mathrm{\#},\alpha ,\phi (\mathrm{\#},\alpha +1,Z,0)[n],Z)$
4. $\phi (\mathrm{\#},\alpha +1,Z,\beta +1)[0]=\phi (\mathrm{\#},\alpha +1,Z,\beta )+1$
5. $\phi (\mathrm{\#},\alpha +1,Z,\beta +1)[n+1]=\phi (\mathrm{\#},\alpha ,\phi (\mathrm{\#},\alpha +1,Z,\beta +1)[n],Z)$
6. 对于极限序数$\beta$，$\phi (\mathrm{\#},\alpha ,Z,\beta )[n]=\phi (\mathrm{\#},\alpha ,Z,\beta [n])$
7. 对于极限序数 $\alpha$,$\phi (\mathrm{\#},\alpha ,Z,0)[n]=\phi (\mathrm{\#},\alpha [n],Z,0)$
8. 对于极限序数 $\alpha$,$\phi (\mathrm{\#},\alpha ,Z,\beta +1)[n]=\phi (\mathrm{\#},\alpha [n],\phi (\mathrm{\#},\alpha ,Z,\beta )+1,Z)$

展开举例

例1.考虑表达式$\phi (1,2,0,0)$，有$\phi (1,2,0,0)[n]=\phi (1,1,\phi (1,1,\cdots \phi (1,1,0,0)\cdots ,0),0)$

例2.考虑表达式$\phi (1,\phi (2,0,1),1)$，我们有

$\begin{array}{rl}\phi (1,\phi (2,0,1),1)[n]& =\phi (1,\phi (2,0,1)[n],\phi (1,\phi (2,0,1),0)+1)\\ & =\phi (1,\phi (2,0,1)[n],\phi (2,0,1)+1)\\ & =\phi (1,\phi (1,\phi (1,\cdots \phi (2,0,0)+1\cdots ,0),0),\phi (2,0,1)+1)\\ \end{array}$

序数元 Veblen 函数

约定

在有限元 Veblen 函数中，我们从右往左给每个变量标号，最右边的元素称为第0项。

若第$\beta$项的值为$\alpha$，则记这一项为\(\alpha\text{@}\beta\)。

即\(\varphi(\alpha_n,\alpha_{n-1},\cdots,\alpha_1,\beta)=\varphi(\alpha_n\text{@}n,\alpha_{n-1}\text{@}(n-1),\cdots,\alpha_1\text{@}1,\beta\text{@}0)\)。

也有时将这个表达式记为$\left(\begin{array}{ccccc}{\alpha }_n& {\alpha }_{n-1}& \cdots & {\alpha }_1& \beta \\ n& n-1& \cdots & 1& 0\end{array}\right)$。

我们可以省略值为0的项，例如$\phi (1,0,0,0,0,3,0,6)$可写为\(\varphi(1\text{@}7,3\text{@}2,6\text{@}0)\)。

序数元 Veblen 函数将元素的"位置"拓展为任意序数，但只允许有限个位置非零。

规则

和有限元 Veblen 函数类似，序数元 Veblen 函数的展开规则只和最右边两个非零项有关。其基本列定义如下：

1. \(\varphi(\#,(\alpha+1)\text{@}(\beta+1),0\text{@}0)[0]=0\)
2. \(\varphi(\#,(\alpha+1)\text{@}(\beta+1),0\text{@}0)[n+1]=\varphi(\#,\alpha\text{@}(\beta+1),\varphi(\#,(\alpha+1)\text{@}(\beta+1),0\text{@}0)[n]\text{@}\beta)\)
3. \(\varphi(\#,(\alpha+1)\text{@}(\beta+1),(\gamma+1)\text{@}0)[0]=\varphi(\#,(\alpha+1)\text{@}(\beta+1),\gamma\text{@}0)+1\)
4. \(\varphi(\#,(\alpha+1)\text{@}(\beta+1),(\gamma+1)\text{@}0)[n+1]=\varphi(\#,\alpha\text{@}(\beta+1),\varphi(\#,(\alpha+1)\text{@}(\beta+1),(\gamma+1)\text{@}0)[n]\text{@}\beta)\)
5. 对于极限序数\(\alpha\)，\(\varphi(\#,\alpha\text{@}\beta)[n]=\varphi(\#,\alpha[n]\text{@}\beta)\)
6. 对于极限序数\(\alpha\)，\(\varphi(\#,\alpha\text{@}(\beta+1),(\gamma+1)\text{@}0)[n]=\varphi(\#,\alpha[n]\text{@}(\beta+1),(\varphi(\#,\alpha\text{@}(\beta+1),\gamma\text{@}0)+1)\text{@}\beta)\)
7. 对于极限序数\(\beta\)，\(\varphi(\#,(\alpha+1)\text{@}\beta,0\text{@}0)[n]=\varphi(\#,\alpha\text{@}\beta,1\text{@}\beta[n])\)
8. 对于极限序数\(\beta\)，\(\varphi(\#,(\alpha+1)\text{@}\beta,(\gamma+1)\text{@}0)[n]=\varphi(\#,\alpha\text{@}\beta,(\varphi(\#,(\alpha+1)\text{@}\beta,\gamma\text{@}0)+1)\text{@}\beta[n])\)
9. 对于极限序数\(\alpha\)、\(\beta\)，\(\varphi(\#,\alpha\text{@}\beta,(\gamma+1)\text{@}0)[n]=\varphi(\#,\alpha[n]\text{@}\beta,(\varphi(\#,\alpha\text{@}\beta,\gamma\text{@}0)+1)\text{@}\beta[n])\)

展开举例

例1.\(\varphi(2\text{@}\omega)[n]=\varphi(1\text{@}\omega,1\text{@}n)\)。

例2.\(\varphi(1\text{@}\omega,1\text{@}0)[n]=\varphi((\varphi(1\text{@}\omega)+1)\text{@}n)\)。

枚举

$\phi (0)=1$

$\phi (\phi (0))=\omega$

$\phi (\phi (\phi (0)))={\omega }^{\omega }$

$\phi (1,0)==\sup \{\phi (0),\phi (\phi (0)),\phi (\phi (\phi (0))),\cdots \}=\sup \{1,\omega ,{\omega }^{\omega },\cdots \}={\epsilon }_0$

$\phi (1,1)=\sup \{\phi (1,0)+1,\phi (\phi (1,0)+1),\phi (\phi (\phi (1,0)+1)),\cdots \}=\sup \{{\epsilon }_0+1,{\omega }^{{\epsilon }_0+1},{\omega }^{\omega }{}^{{\epsilon }_0+1},\cdots \}={\epsilon }_1$

$\phi (1,2)=\sup \{\phi (1,1)+1,\phi (\phi (1,1)+1),\phi (\phi (\phi (1,1)+1)),\cdots \}=\sup \{{\epsilon }_1+1,{\omega }^{{\epsilon }_1+1},{\omega }^{\omega }{}^{{\epsilon }_1+1},\cdots \}={\epsilon }_2$

可以看到，$\phi (1,x)={\epsilon }_x$，它们都枚举$x\mapsto {\omega }^x$的不动点。

$\phi (2,0)=\sup \{\phi (1,0),\phi (1,\phi (1,0)),\phi (1,\phi (1,\phi (1,0))),\cdots \}=\sup \{{\epsilon }_0,{\epsilon }_{\epsilon }{}_0,{\epsilon }_{\epsilon }{}_{\epsilon }{}_0,\cdots \}={\zeta }_0$

$\phi (2,1)=\sup \{\phi (2,0)+1,\phi (1,\phi (2,0)+1),\phi (1,\phi (1,\phi (2,0)+1)),\cdots \}=\sup \{{\zeta }_0+1,{\epsilon }_{{\zeta }_0+1},{\epsilon }_{\epsilon }{}_{{\zeta }_0+1},\cdots \}={\zeta }_1$

故$\phi (2,x)={\zeta }_x$，它们都枚举$x\mapsto {\epsilon }_x$的不动点。

类似地，我们有$\phi (3,x)={\eta }_x$，$\phi (4,x)$为$x\mapsto {\eta }_x$的第$1+x$个不动点。

有名字的序数

二元 Veblen 函数的极限$\sup \{\phi (1,0),\phi (\phi (1,0),0),\cdots \}=\phi (1,0,0)$，被记为FSO(Feferman-Schutte ordinal)；

有限元 Veblen 函数的极限\(\sup\{\varphi(1\text{@}n)\}=\varphi(1\text{@}\omega)\)，被记为SVO(Small Veblen ordinal)；

序数元 Veblen 函数的极限为函数\(x\mapsto\varphi(1\text{@}x)\)的第一个不动点，被记为LVO(Large Veblen ordinal)。