Veblen 函数

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

定义

二元 Veblen 函数

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

二元 Veblen 函数 $φ (α, β) (α, β \in O r d)$ 的定义如下：

$φ (0, β) = φ (β) = ω^{β}$
$φ (α + 1, β)$ 是函数 $x \mapsto φ (α, x)$ 的第 $1 + β$ 个不动点。
对于极限序数 $α$ , $φ (α, β)$ 为所有 $x \mapsto φ (γ, x) (γ < α)$ 的第 $1 + β$ 个公共不动点。

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

0是合法表达式；
若 $α, β$ 是合法表达式，则 $α + β$ 也是合法表达式；
若 $α, β$ 是合法表达式，则 $φ (α, β)$ 也是合法表达式。

其基本列定义如下：

$(φ (α_{1}, β_{1}) + φ (α_{2}, β_{2}) + \dots + φ (α_{k}, β_{k})) [n] = φ (α_{1}, β_{1}) + φ (α_{2}, β_{2}) + \dots + φ (α_{k}, β_{k}) [n]$
$φ (0, 0) = 1$
$φ (0, β + 1) [n] = φ (0, β) \cdot n$
对于极限序数 $β$ , $φ (α, β) [n] = φ (α, β [n])$
$φ (α + 1, 0) [0] = 0$
$φ (α + 1, 0) [n + 1] = φ (α, φ (α + 1, 0) [n])$
$φ (α + 1, β + 1) [0] = φ (α + 1, β) + 1$
$φ (α + 1, β + 1) [n + 1] = φ (α, φ (α + 1, β + 1) [n])$
对于极限序数 $α$ , $φ (α, 0) [n] = φ (α [n], 0)$
对于极限序数 $α$ , $φ (α, β + 1) [n] = φ (α [n], φ (α, β) + 1)$

有限元 Veblen 函数

约定

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

对于表达式 $φ (α_{n}, α_{n - 1}, \dots, α_{1}, β)$ ，记 $k$ 为使 $α_{k} \neq 0$ 的最小正整数，令 $# = α_{n}, \dots, α_{k + 1}$ , $Z = α_{k - 1}, \dots, α_{1}$ ，则该表达式可记为 $φ (#, α_{k}, Z, β)$ 。

规则

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

$φ (Z, #) = φ (#)$
$φ (#, α + 1, Z, 0) [0] = 0$
$φ (#, α + 1, Z, 0) [n + 1] = φ (#, α, φ (#, α + 1, Z, 0) [n], Z)$
$φ (#, α + 1, Z, β + 1) [0] = φ (#, α + 1, Z, β) + 1$
$φ (#, α + 1, Z, β + 1) [n + 1] = φ (#, α, φ (#, α + 1, Z, β + 1) [n], Z)$
对于极限序数 $β$ ， $φ (#, α, Z, β) [n] = φ (#, α, Z, β [n])$
对于极限序数 $α$ , $φ (#, α, Z, 0) [n] = φ (#, α [n], Z, 0)$
对于极限序数 $α$ , $φ (#, α, Z, β + 1) [n] = φ (#, α [n], φ (#, α, Z, β) + 1, Z)$

展开举例

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

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

$\begin{aligned} φ (1, φ (2, 0, 1), 1) [n] & = φ (1, φ (2, 0, 1) [n], φ (1, φ (2, 0, 1), 0) + 1) \\ = φ (1, φ (2, 0, 1) [n], φ (2, 0, 1) + 1) \\ = φ (1, φ (1, φ (1, \dots φ (2, 0, 0) + 1 \dots, 0), 0), φ (2, 0, 1) + 1) \end{aligned}$

序数元 Veblen 函数

约定

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

若第 $β$ 项的值为 $α$ ，则记这一项为$\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)$。

也有时将这个表达式记为 $(\begin{matrix} α_{n} & α_{n - 1} & \dots & α_{1} & β \\ n & n - 1 & \dots & 1 & 0 \end{matrix})$ 。

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

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

规则

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

$\varphi(\#,(\alpha+1)\text{@}(\beta+1),0\text{@}0)[0]=0$
$\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)$
$\varphi(\#,(\alpha+1)\text{@}(\beta+1),(\gamma+1)\text{@}0)[0]=\varphi(\#,(\alpha+1)\text{@}(\beta+1),\gamma\text{@}0)+1$
$\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)$
对于极限序数$\alpha$，$\varphi(\#,\alpha\text{@}\beta)[n]=\varphi(\#,\alpha[n]\text{@}\beta)$
对于极限序数$\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)$
对于极限序数$\beta$，$\varphi(\#,(\alpha+1)\text{@}\beta,0\text{@}0)[n]=\varphi(\#,\alpha\text{@}\beta,1\text{@}\beta[n])$
对于极限序数$\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])$
对于极限序数$\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)$。

枚举

$φ (0) = 1$

$φ (φ (0)) = ω$

$φ (φ (φ (0))) = ω^{ω}$

$φ (1, 0) = = \sup {φ (0), φ (φ (0)), φ (φ (φ (0))), \dots} = \sup {1, ω, ω^{ω}, \dots} = ε_{0}$

$φ (1, 1) = \sup {φ (1, 0) + 1, φ (φ (1, 0) + 1), φ (φ (φ (1, 0) + 1)), \dots} = \sup {ε_{0} + 1, ω^{ε_{0} + 1}, ω^{ω}^{ε_{0} + 1}, \dots} = ε_{1}$

$φ (1, 2) = \sup {φ (1, 1) + 1, φ (φ (1, 1) + 1), φ (φ (φ (1, 1) + 1)), \dots} = \sup {ε_{1} + 1, ω^{ε_{1} + 1}, ω^{ω}^{ε_{1} + 1}, \dots} = ε_{2}$

可以看到， $φ (1, x) = ε_{x}$ ，它们都枚举 $x \mapsto ω^{x}$ 的不动点。

$φ (2, 0) = \sup {φ (1, 0), φ (1, φ (1, 0)), φ (1, φ (1, φ (1, 0))), \dots} = \sup {ε_{0}, ε_{ε}_{0}, ε_{ε}_{ε}_{0}, \dots} = ζ_{0}$

$φ (2, 1) = \sup {φ (2, 0) + 1, φ (1, φ (2, 0) + 1), φ (1, φ (1, φ (2, 0) + 1)), \dots} = \sup {ζ_{0} + 1, ε_{ζ_{0} + 1}, ε_{ε}_{ζ_{0} + 1}, \dots} = ζ_{1}$

故 $φ (2, x) = ζ_{x}$ ，它们都枚举 $x \mapsto ε_{x}$ 的不动点。

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

有名字的序数

二元 Veblen 函数的极限 $\sup {φ (1, 0), φ (φ (1, 0), 0), \dots} = φ (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)。