查看“︁Veblen 函数”︁的源代码

'''Veblen 函数（别名：<math>\varphi</math> 函数）'''是一个 <math>\rm Ord\rightarrow Ord</math> 的序数函数，由美国数学家 Oswald 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>\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>也是合法表达式。

其基本列定义如下：
# <math>(\varphi(\alpha_1,\beta_1)+\varphi(\alpha_2,\beta_2)+\cdots+\varphi(\alpha_k,\beta_k))[n]=\varphi(\alpha_1,\beta_1)+\varphi(\alpha_2,\beta_2)+\cdots+\varphi(\alpha_k,\beta_k)[n]</math>
# <math>\varphi(0,0)=1</math>
# <math>\varphi(0,\beta+1)[n]=\varphi(0,\beta)\cdot n</math>
# 对于极限序数 <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>
# 对于极限序数 <math>\alpha</math>,<math>\varphi(\alpha,0)[n]=\varphi(\alpha[n],0)</math>
# 对于极限序数 <math>\alpha</math>,<math>\varphi(\alpha,\beta+1)[n]=\varphi(\alpha[n],\varphi(\alpha,\beta)+1)</math>

=== 有限元 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)。

{{默认排序:序数记号}}
[[分类:记号]]