Veblen 函数：修订间差异

←上一编辑

可视化wikitext

2025年8月25日 (一) 13:37的最新版本

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

@@ 第1行： / 第1行： @@
-'''Veblen函数（别名：<math>\varphi</math> 函数）'''是一个 <math>\rm Ord\rightarrow Ord</math> 的序数函数，由美国数学家 Oswald Veblen 定义。
+'''Veblen 函数（别名：<math>\varphi</math> 函数）'''是一个 <math>\rm Ord\rightarrow Ord</math> 的序数函数，由美国数学家 Oswald Veblen 定义。
 == 定义 ==
 === 二元 Veblen 函数 ===
-Veblen 函数的定义基于序数函数的[[不动点]].
+Veblen 函数的定义基于序数函数的[[不动点]]。
 二元 Veblen 函数<math>\varphi(\alpha,\beta)~(\alpha,\beta\in\mathrm{Ord})</math>的定义如下：
 # <math>\varphi(0,\beta)=\varphi(\beta)=\omega^\beta</math>
-# <math>\varphi(\alpha+1,\beta)</math> 是函数 <math>x\mapsto\varphi(\alpha,x)</math>的第 <math>1+\beta</math> 个不动点.
+# <math>\varphi(\alpha+1,\beta)</math> 是函数 <math>x\mapsto\varphi(\alpha,x)</math>的第 <math>1+\beta</math> 个不动点。
-# 对于[[序数#极限序数|极限序数]] <math>\alpha</math>,<math>\varphi(\alpha,\beta)</math> 为所有 <math>x\mapsto\varphi(\gamma,x)(\gamma<\alpha)</math> 的第 <math>1+\beta</math> 个公共不动点.
+# 对于[[序数#极限序数|极限序数]] <math>\alpha</math>,<math>\varphi(\alpha,\beta)</math> 为所有 <math>x\mapsto\varphi(\gamma,x)(\gamma<\alpha)</math> 的第 <math>1+\beta</math> 个公共不动点。
+Veblen 函数作为一个序数记号，其合法表达式可按以下方式递归定义：
+# 0是合法表达式；
+# 若<math>\alpha,\beta</math>是合法表达式，则<math>\alpha+\beta</math>也是合法表达式；
+# 若<math>\alpha,\beta</math>是合法表达式，则<math>\varphi(\alpha,\beta)</math>也是合法表达式。
 其基本列定义如下：
@@ 第18行： / 第24行： @@
 # 对于极限序数 <math>\beta</math>,<math>\varphi(\alpha,\beta)[n]=\varphi(\alpha,\beta[n])</math>
 # <math>\varphi(\alpha+1,0)[0]=0</math>
+# <math>\varphi(\alpha+1,0)[n+1]=\varphi(\alpha,\varphi(\alpha+1,0)[n])</math>
 # <math>\varphi(\alpha+1,\beta+1)[0]=\varphi(\alpha+1,\beta)+1</math>
 # <math>\varphi(\alpha+1,\beta+1)[n+1]=\varphi(\alpha,\varphi(\alpha+1,\beta+1)[n])</math>
@@ 第24行： / 第31行： @@
 === 有限元 Veblen 函数 ===
+==== 约定 ====
+我们使用一些缩写："#"表示任意序列，"Z"表示由若干个0构成序列，这两个记号均可以表示空序列。
+对于表达式<math>\varphi(\alpha_n,\alpha_{n-1},\cdots,\alpha_1,\beta)</math>，记<math>k</math>为使<math>\alpha_k\ne 0</math>的最小正整数，令<math>\#=\alpha_n,\cdots,\alpha_{k+1}</math>,<math>Z=\alpha_{k-1},\cdots,\alpha_1</math>，则该表达式可记为<math>\varphi(\#,\alpha_k,Z,\beta)</math>。
+==== 规则 ====
+有限元 Veblen 函数的基本列定义如下：
+# <math>\varphi(Z,\#)=\varphi(\#)</math>
+# <math>\varphi(\#,\alpha+1,Z,0)[0]=0</math>
+# <math>\varphi(\#,\alpha+1,Z,0)[n+1]=\varphi(\#,\alpha,\varphi(\#,\alpha+1,Z,0)[n],Z)</math>
+# <math>\varphi(\#,\alpha+1,Z,\beta+1)[0]=\varphi(\#,\alpha+1,Z,\beta)+1</math>
+# <math>\varphi(\#,\alpha+1,Z,\beta+1)[n+1]=\varphi(\#,\alpha,\varphi(\#,\alpha+1,Z,\beta+1)[n],Z)</math>
+# 对于极限序数<math>\beta</math>，<math>\varphi(\#,\alpha,Z,\beta)[n]=\varphi(\#,\alpha,Z,\beta[n])</math>
+# 对于极限序数 <math>\alpha</math>,<math>\varphi(\#,\alpha,Z,0)[n]=\varphi(\#,\alpha[n],Z,0)</math>
+# 对于极限序数 <math>\alpha</math>,<math>\varphi(\#,\alpha,Z,\beta+1)[n]=\varphi(\#,\alpha[n],\varphi(\#,\alpha,Z,\beta)+1,Z)</math>
+==== 展开举例 ====
+例1.考虑表达式<math>\varphi(1,2,0,0)</math>，有<math>\varphi(1,2,0,0)[n]=\varphi(1,1,\varphi(1,1,\cdots\varphi(1,1,0,0)\cdots,0),0)</math>
+例2.考虑表达式<math>\varphi(1,\varphi(2,0,1),1)</math>，我们有
+<math>\begin{align}
+\varphi(1,\varphi(2,0,1),1)[n]
+&=\varphi(1,\varphi(2,0,1)[n],\varphi(1,\varphi(2,0,1),0)+1)\\
+&=\varphi(1,\varphi(2,0,1)[n],\varphi(2,0,1)+1)\\
+&=\varphi(1,\varphi(1,\varphi(1,\cdots\varphi(2,0,0)+1\cdots,0),0),\varphi(2,0,1)+1)\\
+\end{align}</math>
 === 序数元 Veblen 函数 ===
+==== 约定 ====
+在有限元 Veblen 函数中，我们从右往左给每个变量标号，最右边的元素称为第0项。
+若第<math>\beta</math>项的值为<math>\alpha</math>，则记这一项为\(\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)\)。
+也有时将这个表达式记为<math>\begin{pmatrix}
+\alpha_n&\alpha_{n-1}&\cdots&\alpha_1&\beta\\
+n&n-1&\cdots&1&0
+\end{pmatrix}</math>。
+我们可以省略值为0的项，例如<math>\varphi(1,0,0,0,0,3,0,6)</math>可写为\(\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)\)。
+== 枚举 ==
+<math>\varphi(0)=1</math>
+<math>\varphi(\varphi(0))=\omega</math>
+<math>\varphi(\varphi(\varphi(0)))=\omega^\omega</math>
+<math>\varphi(1,0)=
+=\sup\{\varphi(0),\varphi(\varphi(0)),\varphi(\varphi(\varphi(0))),\cdots\}
+=\sup\{1,\omega,\omega^\omega,\cdots\}
+=\varepsilon_0</math>
+<math>\varphi(1,1)
+=\sup\{\varphi(1,0)+1,\varphi(\varphi(1,0)+1),\varphi(\varphi(\varphi(1,0)+1)),\cdots\}
+=\sup\{\varepsilon_0+1,\omega^{\varepsilon_0+1},\omega^\omega^{\varepsilon_0+1},\cdots\}
+=\varepsilon_1</math>
+<math>\varphi(1,2)
+=\sup\{\varphi(1,1)+1,\varphi(\varphi(1,1)+1),\varphi(\varphi(\varphi(1,1)+1)),\cdots\}
+=\sup\{\varepsilon_1+1,\omega^{\varepsilon_1+1},\omega^\omega^{\varepsilon_1+1},\cdots\}
+=\varepsilon_2</math>
+可以看到，<math>\varphi(1,x)=\varepsilon_x</math>，它们都枚举<math>x\mapsto\omega^x</math>的不动点。
+<math>\varphi(2,0)
+=\sup\{\varphi(1,0),\varphi(1,\varphi(1,0)),\varphi(1,\varphi(1,\varphi(1,0))),\cdots\}
+=\sup\{\varepsilon_0,\varepsilon_\varepsilon_0,\varepsilon_\varepsilon_\varepsilon_0,\cdots\}
+=\zeta_0</math>
+<math>\varphi(2,1)
+=\sup\{\varphi(2,0)+1,\varphi(1,\varphi(2,0)+1),\varphi(1,\varphi(1,\varphi(2,0)+1)),\cdots\}
+=\sup\{\zeta_0+1,\varepsilon_{\zeta_0+1},\varepsilon_\varepsilon_{\zeta_0+1},\cdots\}
+=\zeta_1</math>
+故<math>\varphi(2,x)=\zeta_x</math>，它们都枚举<math>x\mapsto\varepsilon_x</math>的不动点。
+类似地，我们有<math>\varphi(3,x)=\eta_x</math>，<math>\varphi(4,x)</math>为<math>x\mapsto\eta_x</math>的第<math>1+x</math>个不动点。
+== 有名字的序数 ==
+二元 Veblen 函数的极限<math>\sup\{\varphi(1,0),\varphi(\varphi(1,0),0),\cdots\}=\varphi(1,0,0)</math>，被记为[[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)。
+{{默认排序:序数记号}}
 [[分类:记号]]