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)$。

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

规则