Googology Wiki - 用户贡献 [zh-cn]

超限 -1-Y VS Veblen 函数

2025-07-28T11:27:33Z

GaoKao：创建页面，内容为“本条目展示超限(-1)-Y和Veblen函数的列表分析。 {| class="wikitable" !超限(-1)-Y !Veblen函数 |- |<math>(1,\omega)</math> |<math>\varphi(1,0)</math> |- |<math>(1,\omega,1)</math> |<math>\varphi(1,0)+1</math> |- |<math>(1,\omega,1,\omega)</math> |<math>\varphi(1,0)+\varphi(1,0)</math> |- |<math>(1,\omega,2)</math> |<math>\varphi(\varphi(1,0)+1)</math> |- |<math>(1,\omega,2,1,\omega,2)</math> |<math>\varphi(\varphi(1,0)+1)+\varphi(\varphi(…”

本条目展示[[超限(-1)-Y]]和[[Veblen函数]]的列表分析。
{| class="wikitable"
!超限(-1)-Y
!Veblen函数
|-
|<math>(1,\omega)</math>
|<math>\varphi(1,0)</math>
|-
|<math>(1,\omega,1)</math>
|<math>\varphi(1,0)+1</math>
|-
|<math>(1,\omega,1,\omega)</math>
|<math>\varphi(1,0)+\varphi(1,0)</math>
|-
|<math>(1,\omega,2)</math>
|<math>\varphi(\varphi(1,0)+1)</math>
|-
|<math>(1,\omega,2,1,\omega,2)</math>
|<math>\varphi(\varphi(1,0)+1)+\varphi(\varphi(1,0)+1)</math>
|-
|<math>(1,\omega,2,2)</math>
|<math>\varphi(\varphi(1,0)+2)</math>
|-
|<math>(1,\omega,2,3)</math>
|<math>\varphi(\varphi(1,0)+\omega)</math>
|-
|<math>(1,\omega,2,4)</math>
|<math>\varphi(\varphi(1,0)+\omega^\omega)</math>
|-
|<math>(1,\omega,2,\omega)</math>
|<math>\varphi(\varphi(1,0)+\varphi(1,0))</math>
|-
|<math>(1,\omega,2,\omega,2,\omega)</math>
|<math>\varphi(\varphi(1,0)+\varphi(1,0)+\varphi(1,0))</math>
|-
|<math>(1,\omega,3)</math>
|<math>\varphi(\varphi(\varphi(1,0)+1))</math>
|-
|<math>(1,\omega,3,2,\omega)</math>
|<math>\varphi(\varphi(\varphi(1,0)+1)+\varphi(1,0))</math>
|-
|<math>(1,\omega,3,2,\omega,3)</math>
|<math>\varphi(\varphi(\varphi(1,0)+1)+\varphi(\varphi(1,0)+1))</math>
|-
|<math>(1,\omega,3,3)</math>
|<math>\varphi(\varphi(\varphi(1,0)+2))</math>
|-
|<math>(1,\omega,3,4)</math>
|<math>\varphi(\varphi(\varphi(1,0)+\omega))</math>
|-
|<math>(1,\omega,3,\omega)</math>
|<math>\varphi(\varphi(\varphi(1,0)+\varphi(1,0)))</math>
|-
|<math>(1,\omega,4)</math>
|<math>\varphi(\varphi(\varphi(\varphi(1,0)+1)))</math>
|-
|<math>(1,\omega,\omega)</math>
|<math>\varphi(1,1)</math>
|-
|<math>(1,\omega,\omega,2)</math>
|<math>\varphi(\varphi(1,1)+1)</math>
|-
|<math>(1,\omega,\omega,2,\omega)</math>
|<math>\varphi(\varphi(1,1)+\varphi(1,0))</math>
|-
|<math>(1,\omega,\omega,2,\omega,\omega)</math>
|<math>\varphi(\varphi(1,1)+\varphi(1,1))</math>
|-
|<math>(1,\omega,\omega,3)</math>
|<math>\varphi(\varphi(\varphi(1,1)+1))</math>
|-
|<math>(1,\omega,\omega,4)</math>
|<math>\varphi(\varphi(\varphi(\varphi(1,1)+1)))</math>
|-
|<math>(1,\omega,\omega,\omega)</math>
|<math>\varphi(1,2)</math>
|-
|<math>(1,\omega+1)</math>
|<math>\varphi(1,\omega)</math>
|-
|<math>(1,\omega+1,\omega)</math>
|<math>\varphi(1,\omega+1)</math>
|-
|<math>(1,\omega+1,\omega,\omega+1)</math>
|<math>\varphi(1,\omega 2)</math>
|-
|<math>(1,\omega+1,\omega+1)</math>
|<math>\varphi(1,\omega^2)</math>
|-
|<math>(1,\omega+2)</math>
|<math>\varphi(1,\omega^\omega)</math>
|-
|<math>(1,\omega 2)</math>
|<math>\varphi(1,\varphi(1,0))</math>
|-
|<math>(1,\omega 2,\omega,\omega 2)</math>
|<math>\varphi(1,\varphi(1,0)+\varphi(1,0))</math>
|-
|<math>(1,\omega 2,\omega+1)</math>
|<math>\varphi(1,\varphi(\varphi(1,0)+1))</math>
|-
|<math>(1,\omega 2,\omega 2)</math>
|<math>\varphi(1,\varphi(1,1))</math>
|-
|<math>(1,\omega 2+1)</math>
|<math>\varphi(1,\varphi(1,\omega))</math>
|-
|<math>(1,\omega 2+2)</math>
|<math>\varphi(1,\varphi(1,\omega^\omega))</math>
|-
|<math>(1,\omega 3)</math>
|<math>\varphi(1,\varphi(1,\varphi(1,0)))</math>
|-
|<math>(1,\omega^2)</math>
|<math>\varphi(2,0)</math>
|-
|<math>(1,\omega^2,\omega)</math>
|<math>\varphi(1,\varphi(2,0)+1)</math>
|-
|<math>(1,\omega^2,\omega 2)</math>
|<math>\varphi(1,\varphi(1,\varphi(2,0)+1))</math>
|-
|<math>(1,\omega^2,\omega^2)</math>
|<math>\varphi(2,1)</math>
|-
|<math>(1,\omega^2+1)</math>
|<math>\varphi(2,\omega)</math>
|-
|<math>(1,\omega^2+\omega)</math>
|<math>\varphi(2,\varphi(1,0))</math>
|-
|<math>(1,\omega^22)</math>
|<math>\varphi(2,\varphi(2,0))</math>
|-
|<math>(1,\omega^3)</math>
|<math>\varphi(3,0)</math>
|-
|<math>(1,\omega^\omega)</math>
|<math>\varphi(\omega,0)</math>
|-
|<math>(1,\omega^\omega,1+\omega^n)</math>
|<math>\varphi(n,\varphi(\omega,0)+1)</math>
|-
|<math>(1,\omega^\omega,\omega^\omega)</math>
|<math>\varphi(\omega,1)</math>
|-
|<math>(1,\omega^{\omega+1})</math>
|<math>\varphi(\omega+1,0)</math>
|-
|<math>(1,\omega^{\omega^\omega})</math>
|<math>\varphi(\omega^\omega,0)</math>
|-
|<math>(1,(1,\omega))</math>
|<math>\varphi(\varphi(1,0),0)</math>
|-
|<math>(1,(1,(1,\omega)))</math>
|<math>\varphi(\varphi(\varphi(1,0),0),0)</math>
|-
|<math>\mathrm{Limit}=(1,(1,(1,\cdots)))</math>
|<math>\varphi(1,0,0)</math>
|}
[[分类:分析]]

Y序列

2025-07-23T11:09:38Z

GaoKao：/* 展开 */

'''Y序列'''，一般指'''1-Y'''，一种[[Beklemishev's Worm|Worm]]型序数记号。

== 定义 ==

=== 合法表达式 ===
一个合法的 1-Y 表达式是以 1 开头的正整数序列，即形如

<math>(a_1,a_2,\cdots,a_n)\quad(n,a_1,a_2,\cdots,a_n\in\N,a_1=1)</math>

的序列。

例如：<math>(1,4,6,4)</math>和<math>(1,1,4,5,1,4)</math>都是合法的 1-Y 表达式，而<math>(1,2,\pi)</math>不是。

=== 结构 ===
1-Y的合法表达式可分为'''零表达式'''、'''后继表达式'''和'''极限表达式'''。

* '''零表达式'''指<math>n=0</math>的表达式，即空序列；
* '''后继表达式'''指<math>n>0,a_n=1</math>的表达式，即末项为1的非空序列；
* '''极限表达式'''指<math>n>0,a_n>1</math>的表达式，末项不为1的非空序列。

对于 1-Y 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，定义以下术语：

==== 行标与列标 ====
设想我们在一个无限大的矩阵下工作，从左往右是第1,2,...列，从下往上是第0,1,...行。'''与0-Y不同的是：
* 行标现在可以是一个超限序数，例如第<math>\omega</math>行。
* 一些项现在可以不赋予任何数作为取值，这些项称为空项，记作<math>\varnothing</math>。'''
第<math>\alpha</math>行第<math>j</math>列的项记为<math>x_{\alpha,j}</math>。

初始时，我们有<math>x_{0,j}=a_j</math>，<math>1\leq{j}\leq{n}</math>。

==== 后继序数行的父项 & 阶差项 ====
对于后继序数<math>\alpha+1</math>和非空项<math>x_{\alpha+1,j}</math>，它的父项是与它位于同一行，且满足以下条件的最右侧非空项<math>x_{\alpha+1,k}</math>：

* <math>k<j</math>且<math>x_{\alpha+1,k}<x_{\alpha+1,j}</math>。
* <math>x_{\alpha,k}</math>是<math>x_{\alpha,j}</math>的祖先项。

这里“祖先项”的定义类似于[[Bashicu矩阵|BMS]]：一个元素自己，以及它的父项、父项的父项、父项的父项的父项......共同构成它的祖先项。

对于第0行的项<math>x_{0,j}</math>，它的父项是与它位于同一行，且同时满足<math>k<j</math>和<math>x_{0,k}<x_{0,j}</math>的最右侧项<math>x_{0,k}</math>。

如果满足上述条件的项不存在，那么<math>x_{\alpha+1,j}</math>(或者<math>x_{0,j}</math>)的父项不存在。特别地，等于1的项的父项不存在。

对于任何序数<math>\alpha</math>，项<math>x_{\alpha,j}</math>：
* 如果它有父项<math>x_{\alpha,k}</math>，则它的阶差项为<math>x_{\alpha+1,j}=x_{\alpha,j}-x_{\alpha,k}</math>。
* 如果它没有父项，或者为空项，它的阶差项为<math>x_{\alpha,j}=\varnothing</math>。

由于第<math>\alpha</math>行的项的阶差项构成了第<math>\alpha+1</math>行，称第<math>\alpha+1</math>行的序列是第<math>\alpha</math>行的序列的'''阶差序列'''。

==== 极限序数行的父项 & 提取 ====
上述定义只给出了后继序数行的项的取值和父项关系。接下来给出极限序数的情形：

设极限序数<math>\alpha=\beta+\omega<\omega^2</math>，<math>\beta</math>为极限序数。则定义项<math>x_{\alpha,j}</math>如下：

取出最大的非负整数<math>p</math>使得<math>x_{\beta+p,j}</math>不为空项，则<math>x_{\alpha,j}=x_{\beta+p,j}</math>。这些项<math>x_{\beta+p,j}</math>称为主项。

对大于1的项<math>x_{\alpha,j}</math>定义如下概念：
# 设<math>x_{\alpha,j}=x_{\beta+p,j}</math>，令<math>a=j</math>。
# 设<math>x_{\beta+p-1,a}</math>的父项为<math>x_{\beta+p-1,k}</math>。如果<math>x_{\beta+p-1,k}</math>是主项，或者<math>x_{\beta+p,k}</math>是主项，称<math>x_{\alpha,k}</math>是<math>x_{\alpha,j}</math>的拟父项。
# 否则令<math>a=k</math>并回到第2步，直到找到某个主项，设其列标是<math>l</math>，称<math>x_{\alpha,l}</math>是<math>x_{\alpha,j}</math>的拟父项。

对于极限序数<math>\alpha</math>和大于1的项<math>x_{\alpha,j}</math>，它的父项是与它位于同一行，且满足以下条件的最右侧项<math>x_{\alpha,k}</math>：

* <math>k<j</math>且<math>x_{\alpha,k}<x_{\alpha,j}</math>。
* <math>x_{\alpha,k}</math>是<math>x_{\alpha,j}</math>的拟祖先项。

这里“拟祖先项”的定义是：一个元素自己，以及它的拟父项、拟父项的拟父项......共同构成它的拟祖先项。

如果满足上述条件的项不存在，那么<math>x_{\alpha,j}</math>的父项不存在。另外，等于1的项的父项不存在。

以上定义项<math>x_{\alpha,j}</math>时，将所有位于<math>\beta</math>到<math>\beta+\omega</math>之间的行中每一列的最上方非空项取了出来，并“提”到了<math>\alpha=\beta+\omega</math>行(还保留了其下的一些父项关系)，这就是'''提取(Extraction)'''的含义。

''注：此处的“主项”，“拟父项/拟祖先项”是编者引入的等价的临时定义。在主流的定义与教程中，通常使用山脉图(见下文)定义此部分内容。''

==== 末列与坏根 ====
第<math>n</math>列称为'''末列'''。

对于末列的某一项<math>x_{\alpha,n}</math>，它的父项设为<math>x_{\alpha,r}</math>。如果在计算到某行(第<math>\gamma</math>行)时有<math>x_{\gamma,n}-x_{\gamma,r}=1</math>，则称<math>a_r</math>为'''坏根'''，称第<math>r</math>列为'''根列'''。

以上给出了 1-Y 极限表达式<math>(a_1,a_2,\cdots,a_n)</math>的完整寻找坏根流程。

== 山脉图 ==
要描述1-Y的展开规则或者直观理解部分定义，需要用到'''山脉图'''的辅助。

1-Y的山脉图作图难度略高于[[0-Y]]。对于 1-Y 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，它的山脉图的画法如下：

先按照寻找坏根的规则逐行向上求出各项，直到某次提取的所有主项全为1，不进行这次提取。

接下来，对于第后继序数<math>\alpha+1</math>行，进行如下操作：

取出所有非空项<math>x_{\alpha+1,j}</math>。对于每个<math>x_{\alpha,j}</math>，用竖直线段连接<math>x_{\alpha+1,j}</math>的下端与<math>x_{\alpha,j}</math>的上端。这些竖直线段称为'''右腿'''，<math>x_{i,j}</math>称为它的端点。

设<math>x_{\alpha,j}</math>有父项<math>x_{\alpha,k}</math>，用斜线段连接<math>x_{\alpha+1,j}</math>的下端与<math>x_{\alpha,k}</math>的上端。这些斜线段称为'''左腿'''，<math>x_{\alpha,k}</math>称为它的端点。

接下来，对于第极限序数<math>\alpha=\beta+\omega</math>行，进行如下操作：

用虚线分别连接所有项<math>x_{\alpha,j}</math>的下端，和它们对应的主项<math>x_{\beta+p,j}</math>的上端。

对所有行各执行一次上述操作，就得到了<math>(a_1,a_2,\cdots,a_n)</math>的山脉图。

注意：有些情况下，山脉图只包含一行，即第0行。

1-Y的山脉图中，从一个有父项的项出发，沿右腿向上走一步，再沿左腿向下走一步，就能到达它的父项。

对于极限序数<math>\alpha</math>行的项<math>x_{\alpha,j}</math>，从其对应的主项<math>x_{\beta+p,j}</math>出发，沿左腿向下走一步，然后在保持行标不大于<math>\beta+p</math>的前提下，沿右腿向上走一步(如果可能)，重复此过程直到找到另一个主项，设其列标是<math>l</math>，则<math>x_{\alpha,l}</math>是<math>x_{\alpha,j}</math>的拟父项。

网站[https://naruyoko.github.io/whYmountain/ whY mountain]可以绘制1-Y的山脉图。

''(待补充附有配图的1-Y山脉图绘制例子,以及绘制1-Y山脉图的网站(有吗),以及极限序数行父项关系的直观理解)''

== 展开 ==
1-Y的展开难度远高于[[0-Y]]。

对于1-Y的极限表达式<math>\mathrm{Y}(a_1,a_2,\cdots,a_n)</math>，其基本列第<math>q</math>项可按以下方式确定：

先作出其山脉图，求出根列<math>r</math>，根列右侧的结构称为'''坏部'''。

设序列一共进行了<math>m</math>次提取操作，此时山脉图被分为<math>m+1</math>层，第<math>k</math>层的行标位于<math>\omega(k-1)</math>和<math>\omega k</math>之间。

1-Y的展开是从上到下逐层进行的。

对于最上面一层，其展开规则和0-Y类似：

# 先将末列行标第二大的项<math>x_{\omega m+p,n}</math>减1(行标最大的项为1)，删除本层坏部第<math>\omega m+p</math>行以下元素的数值。
# 将本层的坏部平移并复制在山脉图末尾，复制<math>q-1</math>次。“坏部平移”是指左右腿及端点同时平移
# 特别地，如果某一条左腿的端点位于根列左侧，复制时左腿的端点不向右平移。
# 接下来，从根列右侧开始从上到下，每一行从左到右填入数字。对于某个位置，若其向上通过右腿移动到值为<math>x</math>的项，然后向左下通过左腿移动到值为<math>y</math>的项，则这个位置应填入<math>x+y</math>。

第<math>k(1\le k \le m)</math>层山脉图的展开需要引入几个概念<ref>Suzuka梅天狸：Y序列专题(4)——让我们请出主角登场(下) ，https://zhuanlan.zhihu.com/p/671375564</ref>：顶点元素、平移边、轮廓边、参考边。

顶点元素的定义如下：从本层根列的主项出发，重复“沿左腿向上走一步，再沿右腿向下走若干步(终点的行标不能低于起点)”，得到的所有主项称为顶点元素。或者说，顶点元素是在提取之后以根列为“拟祖先项”的主项。

平移边、轮廓边、参考边的定义和顶点元素有关：

* '''轮廓边'''：从一个顶点元素出发，重复“沿左腿向上走一步，再沿右腿向下走一步”直至无路可走，中间经过的所有边称为轮廓边。
* '''平移边'''：根列右侧的非轮廓边称为平移边。
* '''参考边'''：从本层根列的主项出发，得到的所有轮廓边称为参考边。取基本列第<math>q</math>项时，根列右边的结构需要循环复制<math>q-1</math>次。在每一轮复制的过程中，三种边的行为如下：

* 平移边只需要简单地向右平移。特别地，若左腿的端点位于根列左侧，则左腿的端点保持不动。这一点和0-Y的规则类似。
* 轮廓边在向右平移的同时，还需要向上提升它的高度。具体来说，提升的高度为最右列和根列顶点元素的高度差。
* 参考边在向右平移后，还要向上复制，用来填补平移边和轮廓边之间的空隙。

在所有的边复制完成之后，我们还是按照从上到下、从左到右的顺序向山脉图填入数字。

首先，本层每一列最上方的项等于上层最底行(即第<math>\omega k</math>行)对应项，即保持虚线两端的对应关系

填充完最上方的数字之后，按照之前相同的规则继续填充其它项，就得到了第<math>k</math>层的山脉图。

从第最上面一层开始，依次对每一层进行复制和填充，直到填充完第1层，得到第0行的序列就是<math>\mathrm{Y}(a_1,a_2,\cdots,a_n)</math>的基本列第<math>q</math>项。

== 枚举 ==
''(开摆!)''

== n-Y序列 ==
通过某种方式，我们可以把1-Y前面的参数1扩展到任意大的自然数<math>n</math>。详细信息请参考[[ω-Y]]页面。

== 参考资料 ==
[[分类:记号]]

Y序列

2025-07-23T08:40:37Z

GaoKao：/* 山脉图 */

'''Y序列'''，一般指'''1-Y'''，一种[[Beklemishev's Worm|Worm]]型序数记号。

== 定义 ==

=== 合法表达式 ===
一个合法的 1-Y 表达式是以 1 开头的正整数序列，即形如

<math>(a_1,a_2,\cdots,a_n)\quad(n,a_1,a_2,\cdots,a_n\in\N,a_1=1)</math>

的序列。

例如：<math>(1,4,6,4)</math>和<math>(1,1,4,5,1,4)</math>都是合法的 1-Y 表达式，而<math>(1,2,\pi)</math>不是。

=== 结构 ===
1-Y的合法表达式可分为'''零表达式'''、'''后继表达式'''和'''极限表达式'''。

* '''零表达式'''指<math>n=0</math>的表达式，即空序列；
* '''后继表达式'''指<math>n>0,a_n=1</math>的表达式，即末项为1的非空序列；
* '''极限表达式'''指<math>n>0,a_n>1</math>的表达式，末项不为1的非空序列。

对于 1-Y 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，定义以下术语：

==== 行标与列标 ====
设想我们在一个无限大的矩阵下工作，从左往右是第1,2,...列，从下往上是第0,1,...行。'''与0-Y不同的是：
* 行标现在可以是一个超限序数，例如第<math>\omega</math>行。
* 一些项现在可以不赋予任何数作为取值，这些项称为空项，记作<math>\varnothing</math>。'''
第<math>\alpha</math>行第<math>j</math>列的项记为<math>x_{\alpha,j}</math>。

初始时，我们有<math>x_{0,j}=a_j</math>，<math>1\leq{j}\leq{n}</math>。

==== 后继序数行的父项 & 阶差项 ====
对于后继序数<math>\alpha+1</math>和非空项<math>x_{\alpha+1,j}</math>，它的父项是与它位于同一行，且满足以下条件的最右侧非空项<math>x_{\alpha+1,k}</math>：

* <math>k<j</math>且<math>x_{\alpha+1,k}<x_{\alpha+1,j}</math>。
* <math>x_{\alpha,k}</math>是<math>x_{\alpha,j}</math>的祖先项。

这里“祖先项”的定义类似于[[Bashicu矩阵|BMS]]：一个元素自己，以及它的父项、父项的父项、父项的父项的父项......共同构成它的祖先项。

对于第0行的项<math>x_{0,j}</math>，它的父项是与它位于同一行，且同时满足<math>k<j</math>和<math>x_{0,k}<x_{0,j}</math>的最右侧项<math>x_{0,k}</math>。

如果满足上述条件的项不存在，那么<math>x_{\alpha+1,j}</math>(或者<math>x_{0,j}</math>)的父项不存在。特别地，等于1的项的父项不存在。

对于任何序数<math>\alpha</math>，项<math>x_{\alpha,j}</math>：
* 如果它有父项<math>x_{\alpha,k}</math>，则它的阶差项为<math>x_{\alpha+1,j}=x_{\alpha,j}-x_{\alpha,k}</math>。
* 如果它没有父项，或者为空项，它的阶差项为<math>x_{\alpha,j}=\varnothing</math>。

由于第<math>\alpha</math>行的项的阶差项构成了第<math>\alpha+1</math>行，称第<math>\alpha+1</math>行的序列是第<math>\alpha</math>行的序列的'''阶差序列'''。

==== 极限序数行的父项 & 提取 ====
上述定义只给出了后继序数行的项的取值和父项关系。接下来给出极限序数的情形：

设极限序数<math>\alpha=\beta+\omega<\omega^2</math>，<math>\beta</math>为极限序数。则定义项<math>x_{\alpha,j}</math>如下：

取出最大的非负整数<math>p</math>使得<math>x_{\beta+p,j}</math>不为空项，则<math>x_{\alpha,j}=x_{\beta+p,j}</math>。这些项<math>x_{\beta+p,j}</math>称为主项。

对大于1的项<math>x_{\alpha,j}</math>定义如下概念：
# 设<math>x_{\alpha,j}=x_{\beta+p,j}</math>，令<math>a=j</math>。
# 设<math>x_{\beta+p-1,a}</math>的父项为<math>x_{\beta+p-1,k}</math>。如果<math>x_{\beta+p-1,k}</math>是主项，或者<math>x_{\beta+p,k}</math>是主项，称<math>x_{\alpha,k}</math>是<math>x_{\alpha,j}</math>的拟父项。
# 否则令<math>a=k</math>并回到第2步，直到找到某个主项，设其列标是<math>l</math>，称<math>x_{\alpha,l}</math>是<math>x_{\alpha,j}</math>的拟父项。

对于极限序数<math>\alpha</math>和大于1的项<math>x_{\alpha,j}</math>，它的父项是与它位于同一行，且满足以下条件的最右侧项<math>x_{\alpha,k}</math>：

* <math>k<j</math>且<math>x_{\alpha,k}<x_{\alpha,j}</math>。
* <math>x_{\alpha,k}</math>是<math>x_{\alpha,j}</math>的拟祖先项。

这里“拟祖先项”的定义是：一个元素自己，以及它的拟父项、拟父项的拟父项......共同构成它的拟祖先项。

如果满足上述条件的项不存在，那么<math>x_{\alpha,j}</math>的父项不存在。另外，等于1的项的父项不存在。

以上定义项<math>x_{\alpha,j}</math>时，将所有位于<math>\beta</math>到<math>\beta+\omega</math>之间的行中每一列的最上方非空项取了出来，并“提”到了<math>\alpha=\beta+\omega</math>行(还保留了其下的一些父项关系)，这就是'''提取(Extraction)'''的含义。

''注：此处的“主项”，“拟父项/拟祖先项”是编者引入的等价的临时定义。在主流的定义与教程中，通常使用山脉图(见下文)定义此部分内容。''

==== 末列与坏根 ====
第<math>n</math>列称为'''末列'''。

对于末列的某一项<math>x_{\alpha,n}</math>，它的父项设为<math>x_{\alpha,r}</math>。如果在计算到某行(第<math>\gamma</math>行)时有<math>x_{\gamma,n}-x_{\gamma,r}=1</math>，则称<math>a_r</math>为'''坏根'''，称第<math>r</math>列为'''根列'''。

以上给出了 1-Y 极限表达式<math>(a_1,a_2,\cdots,a_n)</math>的完整寻找坏根流程。

== 山脉图 ==
要描述1-Y的展开规则或者直观理解部分定义，需要用到'''山脉图'''的辅助。

1-Y的山脉图作图难度略高于[[0-Y]]。对于 1-Y 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，它的山脉图的画法如下：

先按照寻找坏根的规则逐行向上求出各项，直到某次提取的所有主项全为1，不进行这次提取。

接下来，对于第后继序数<math>\alpha+1</math>行，进行如下操作：

取出所有非空项<math>x_{\alpha+1,j}</math>。对于每个<math>x_{\alpha,j}</math>，用竖直线段连接<math>x_{\alpha+1,j}</math>的下端与<math>x_{\alpha,j}</math>的上端。这些竖直线段称为'''右腿'''，<math>x_{i,j}</math>称为它的端点。

设<math>x_{\alpha,j}</math>有父项<math>x_{\alpha,k}</math>，用斜线段连接<math>x_{\alpha+1,j}</math>的下端与<math>x_{\alpha,k}</math>的上端。这些斜线段称为'''左腿'''，<math>x_{\alpha,k}</math>称为它的端点。

接下来，对于第极限序数<math>\alpha=\beta+\omega</math>行，进行如下操作：

用虚线分别连接所有项<math>x_{\alpha,j}</math>的下端，和它们对应的主项<math>x_{\beta+p,j}</math>的上端。

对所有行各执行一次上述操作，就得到了<math>(a_1,a_2,\cdots,a_n)</math>的山脉图。

注意：有些情况下，山脉图只包含一行，即第0行。

1-Y的山脉图中，从一个有父项的项出发，沿右腿向上走一步，再沿左腿向下走一步，就能到达它的父项。

对于极限序数<math>\alpha</math>行的项<math>x_{\alpha,j}</math>，从其对应的主项<math>x_{\beta+p,j}</math>出发，沿左腿向下走一步，然后在保持行标不大于<math>\beta+p</math>的前提下，沿右腿向上走一步(如果可能)，重复此过程直到找到另一个主项，设其列标是<math>l</math>，则<math>x_{\alpha,l}</math>是<math>x_{\alpha,j}</math>的拟父项。

网站[https://naruyoko.github.io/whYmountain/ whY mountain]可以绘制1-Y的山脉图。

''(待补充附有配图的1-Y山脉图绘制例子,以及绘制1-Y山脉图的网站(有吗),以及极限序数行父项关系的直观理解)''

== 展开 ==
1-Y的展开难度远高于[[0-Y]]。

对于1-Y的极限表达式<math>(a_1,a_2,\cdots,a_n)</math>作出其山脉图

''(等待更新)''

== 枚举 ==
''(开摆!)''

== n-Y序列 ==
通过某种方式，我们可以把1-Y前面的参数1扩展到任意大的自然数<math>n</math>。详细信息请参考[[ω-Y]]页面。

== 参考资料 ==
[[分类:记号]]

0-Y

2025-07-22T11:54:26Z

GaoKao：/* 展开 */

'''0-Y'''是一种[[Beklemishev's Worm|Worm]]型序数记号，它是[[初等序列系统|PrSS]]的一种扩展。

== 定义 ==

=== 合法表达式 ===
一个合法的 0-Y 表达式是以 1 开头的正整数序列，即形如

<math>(a_1,a_2,\cdots,a_n)\quad(n,a_1,a_2,\cdots,a_n\in\N,a_1=1)</math>

的序列。

例如：<math>(1,4,6,4)</math>和<math>(1,1,4,5,1,4)</math>都是合法的 0-Y 表达式，而<math>(1,2,\pi)</math>不是。

=== 结构 ===
0-Y的合法表达式可分为'''零表达式'''、'''后继表达式'''和'''极限表达式'''。

* '''零表达式'''指<math>n=0</math>的表达式，即空序列；
* '''后继表达式'''指<math>n>0,a_n=1</math>的表达式，即末项为1的非空序列；
* '''极限表达式'''指<math>n>0,a_n>1</math>的表达式，末项不为1的非空序列。

对于 0-Y 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，定义以下术语：

==== 行标与列标 ====
设想我们在一个无限大的矩阵下工作，从左往右是第1,2,...列，从下往上是第0,1,...行。第<math>i</math>行第<math>j</math>列的项记为<math>x_{i,j}</math>。

初始时，我们有<math>x_{0,j}=a_j</math>，<math>1\leq{j}\leq{n}</math>。

==== 父项与阶差项 ====
等于1的项没有父项。对于大于1的项<math>x_{i,j}</math>，它的父项与它位于同一行，且是满足以下条件的最右侧项<math>x_{i,k}</math>：

* <math>k<j</math>且<math>x_{i,k}<x_{i,j}</math>。
* 如果<math>i>0</math>，还要求<math>x_{i-1,k}</math>是<math>x_{i-1,j}</math>的祖先项。

这里“祖先项”的定义类似于[[Bashicu矩阵|BMS]]：一个元素自己，以及它的父项、父项的父项、父项的父项的父项......共同构成它的祖先项。

对于<math>x_{i,j}</math>，如果它有父项<math>x_{i,k}</math>，则它的阶差项为<math>x_{i+1,j}=x_{i,j}-x_{i,k}</math>；如果<math>x_{i,j}=1</math>，则它的阶差项<math>x_{i+1,j}=1</math>。

由于第<math>i</math>行的项的阶差项构成了第<math>i+1</math>行，称第<math>i+1</math>行的序列是第<math>i</math>行的序列的'''阶差序列'''。

==== 末列与坏根 ====
第<math>n</math>列称为'''末列'''。

对于末列的某一项<math>x_{i,n}</math>，它的父项设为<math>x_{i,r}</math>。如果在计算到某行(第<math>p</math>行)时有<math>x_{p,n}-x_{p,r}=1</math>，则称<math>a_r</math>为'''坏根'''，称第<math>r</math>列为'''根列'''，并且不再计算第<math>p+1</math>行及之后的行。

以上给出了 0-Y 极限表达式<math>(a_1,a_2,\cdots,a_n)</math>的完整寻找坏根流程。

== 山脉图 ==
要描述0-Y的展开规则，需要用到'''山脉图'''的辅助。对于 0-Y 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，它的山脉图的画法如下：

先按照寻找坏根的规则画出第0到<math>p</math>行。现在你有了一个<math>p\times{n}</math>的“矩阵”(第0至第<math>p</math>行，第1至第<math>n</math>列)，接下来，对于第<math>i</math>行，<math>0\leq{i}\leq{p-1}</math>进行如下操作：

对于每个<math>x_{i,j}</math>，用竖直线段连接<math>x_{i+1,j}</math>的下端与<math>x_{i,j}</math>的上端。这些竖直线段称为'''右腿'''，<math>x_{i,j}</math>称为它的端点。

对于每个大于1的<math>x_{i,j}</math>，设<math>x_{i,j}</math>有父项<math>x_{i,k}</math>，用斜线段连接<math>x_{i+1,j}</math>的下端与<math>x_{i,k}</math>的上端。这些斜线段称为'''左腿'''，<math>x_{i,k}</math>称为它的端点。

对第1到第<math>p</math>行各执行一次上述操作，就得到了<math>(a_1,a_2,\cdots,a_n)</math>的山脉图。

山脉图有以下性质：从一个有父项的元素出发，沿右腿向上走一步，再沿左腿向下走一步，就能到达它的父项。

注意：有些情况下，山脉图只包含一行，即第0行。

注：由于山脉图的某一行只和其下的项有关，你也可以在逐行往上填写阶差序列的同时画出山脉图。许多常见的0-Y教程都采用这个方法。
[[文件:0y1463797.png|缩略图]]
以<math>(1,4,6,3,7,9,7)</math>为例，其山脉图如右图所示。由于第2行末项2的阶差为1，故不再继续计算。

''(待补充绘制0-Y山脉图的网站(有吗))''

== 展开 ==
对于 0-Y 的一个表达式<math>(a_1,a_2,\cdots,a_n)</math>：

* 如果它是零表达式，它对应序数0。
* 如果它是后继表达式，它对应<math>(a_1,a_2,\cdots,a_{n-1})</math>的后继。
* 如果它是极限表达式，它的基本列第<math>q</math>项如下确定：

# 作出<math>p\times{n}</math>的山脉图。称位于根列右侧的结构(包括阶差项和其对应的山脉图中的左右腿，不包括根列)为'''坏部'''，其余为'''好部'''。
# 删除坏部中第<math>p</math>行以下的所有项，并将<math>x_{p,n}</math>减1。
# 接下来，保留山脉图的好部不动，将坏部平移并复制在山脉图末尾，复制<math>q-1</math>次。“坏部平移”是指左右腿及端点同时平移。
# 特别地，如果某一条左腿的端点位于根列左侧，复制时左腿的端点不向右平移。
# 接下来，你得到了根列右侧的一系列山脉图和第<math>p</math>行的一系列项。从根列右侧开始，从上到下，每一行从左到右，按照以下方式填入正整数：对于某个位置，向上通过右腿移动到值为<math>x</math>的项，然后向左下通过左腿移动到值为<math>y</math>的项，则回到初始位置并填上<math>x+y</math>。
# 最后得到的第0行的序列，就是<math>(a_1,a_2,\cdots,a_n)</math>展开的基本列第<math>q-1</math>项。

0-Y的极限基本列是<math>\{(1,2),(1,3),(1,4),\cdots\}</math>，从这个基本列中元素开始取前驱或取基本列所能得到的表达式是 0-Y 的标准式。

例1：<math>\mathrm{0-Y}(1,4,6,4)[3]</math>

先作出它的山脉图，从图中可以得到：根列为第1列，坏部为第2、3、4列。
[[文件:0-Y(1,4,6,4).png|居中|缩略图]]
然后，将坏部第2行以下的数删除，并将其整体平移并复制2次。
[[文件:0-Y(1,4,6,4)展开(1).png|居中|缩略图]]
接着，依次向山脉图中的“空位”填入正整数，注意所填的数满足“一个数等于其右腿和左腿连接的数之差”。
[[文件:0-Y(1,4,6,4)展开(2).png|居中|缩略图]]
最后，根据山脉图的第0行，我们得到了<math>\mathrm{0-Y}(1,4,6,4)[3]=\mathrm{0-Y}(1,4,6,3,7,10,6,11,15,10)</math>。

例2：<math>\mathrm{0-Y}(1,4,6,3,7,9,7)[3]</math>

其山脉图已经在[[0-Y#山脉图|前面]]给出。从图中可以得到：根列为第4列，坏部为第5、6、7列。

注意：第2行第6列的“1”的左腿的另一端(位于第1列)在根列左侧，故在复制时，其另一端点保持不动。

复制、填充后得到的山脉图如下。
[[文件:0-Y(1,4,6,3,7,9,7)展开.png|居中|缩略图]]
因此<math>\mathrm{0-Y}(1,4,6,3,7,9,7)[3]=\mathrm{0-Y}(1,4,6,3,7,9,6,11,13,10,16,18,15)</math>

== 枚举 ==
我们使用 [[Bashicu矩阵|BMS]] 对 0-Y 进行简单分析(左边是BMS，右边是0-Y)。

<math>(0)=1</math>

<math>(0)(1)=1,2</math>

<math>(0)(1)(1)=1,2,2</math>

<math>(0)(1)(2)=1,2,3</math>

<math>(0)(1)(2)(3)=1,2,3,4</math>

<math>(0)(1,1)=1,3</math>

<math>(0)(1,1)(1,0)=1,3,2</math>

<math>(0)(1,1)(1,0)(2,1)=1,3,2,4</math>

<math>(0)(1,1)(1,1)=1,3,3</math>

<math>(0)(1,1)(2,0)=1,3,4</math>

<math>(0)(1,1)(2,0)(3,1)=1,3,4,6</math>

<math>(0)(1,1)(2,1)=1,3,5</math>

<math>(0)(1,1)(2,1)(3,1)=1,3,5,7</math>

<math>(0)(1,1)(2,2)=1,3,6</math>

<math>(0)(1,1)(2,2)(3,3)=1,3,6,10</math>

<math>(0)(1,1,1)=1,4</math>

<math>(0)(1,1,1)(1,0,0)(2,1,1)=1,4,2,5</math>

<math>(0)(1,1,1)(1,1,0)=1,4,3</math>

<math>(0)(1,1,1)(1,1,0)(2,2,1)=1,4,3,7</math>

<math>(0)(1,1,1)(1,1,1)=1,4,4</math>

<math>(0)(1,1,1)(2,0,0)=1,4,5</math>

<math>(0)(1,1,1)(2,1,0)=1,4,6</math>

<math>(0)(1,1,1)(2,1,0)(1,1,1)=1,4,6,4</math>

<math>(0)(1,1,1)(2,1,0)(3,1,0)=1,4,6,8</math>

<math>(0)(1,1,1)(2,1,0)(3,2,1)=1,4,6,10</math>

<math>(0)(1,1,1)(2,1,1)=1,4,7</math>

<math>(0)(1,1,1)(2,1,1)(3,1,1)=1,4,7,10</math>

<math>(0)(1,1,1)(2,2,0)=1,4,8</math>

<math>(0)(1,1,1)(2,2,1)=1,4,9</math>

<math>(0)(1,1,1)(2,2,2)=1,4,10</math>

<math>(0)(1,1,1)(2,2,2)(3,3,3)=1,4,10,20</math>

<math>(0)(1,1,1,1)=1,5</math>

<math>(0)(1,1,1,1,1)=1,6</math>

<math>\cdots</math>

两者极限相等。

== 与[[Bashicu矩阵|BMS]]的互译 ==
事实上，0-Y与[[Bashicu矩阵|BMS]]的标准式之间有十分简单的互译关系。

对于一个 0-Y 标准表达式，作出其山脉图，但不考虑末列的影响，而是无限地逐行向上作出阶差序列，直到得到的序列全为1。

现在你有了一个<math>t\times{n}</math>的山脉图，行标为0到<math>t</math>，列标为1到<math>n</math>。

定义<math>b_{i,j}</math>如下：

* <math>x_{i,j}=1</math>时<math>b_{i,j}=0</math>。
*否则设<math>x_{i,j}</math>的父项为<math>x_{i,k}</math>，令<math>b_{i,j}=b_{i,k}+1</math>。

最后得到的矩阵<math>(b_{i,j})</math>删去最顶上全为0的行，并以水平线为轴镜像，即可得到等价的BMS。

对于一个BMS标准式<math>(d_{i,j})</math>(第1至第<math>t</math>行，第1至第<math>n</math>列)，定义<math>e_{i,j}</math>如下：

* <math>d_{i,j}=0</math>时<math>e_{i,j}=1</math>。
* 否则设<math>d_{i,j}</math>的父项为<math>d_{i,k}</math>，令<math>e_{i,j}=e_{i,k}+e_{i+1,j}</math>。如果<math>i=t</math>，我们规定<math>e_{i+1,j}=1</math>。

最后取出<math>f_k=e_{1,k}</math>，即为等价的0-Y序列。

然而，尽管目前已有的分析均支持以上结论，目前对此尚未有严格的证明。

== 与[[Y序列]]的关系 ==
0-Y虽然名字里带有'''Y'''，但它与[[Y序列]]的内核有较大差异。

历史上，0-Y的出现晚于通常的Y序列，而且强度也远低于Y序列。事实上，0-Y是仿照BMS制作出来的。

[[分类:记号]]

文件:0-Y(1,4,6,3,7,9,7)展开.png

2025-07-22T11:24:52Z

GaoKao：

文件:0-Y(1,4,6,4)展开(2).png

2025-07-22T11:19:49Z

GaoKao：

文件:0-Y(1,4,6,4)展开(1).png

2025-07-22T11:17:22Z

GaoKao：

文件:0-Y(1,4,6,4).png

2025-07-22T10:58:37Z

GaoKao：

0-Y

2025-07-22T10:04:41Z

GaoKao：

'''0-Y'''是一种[[Beklemishev's Worm|Worm]]型序数记号，它是[[初等序列系统|PrSS]]的一种扩展。

== 定义 ==

=== 合法表达式 ===
一个合法的 0-Y 表达式是以 1 开头的正整数序列，即形如

<math>(a_1,a_2,\cdots,a_n)\quad(n,a_1,a_2,\cdots,a_n\in\N,a_1=1)</math>

的序列。

例如：<math>(1,4,6,4)</math>和<math>(1,1,4,5,1,4)</math>都是合法的 0-Y 表达式，而<math>(1,2,\pi)</math>不是。

=== 结构 ===
0-Y的合法表达式可分为'''零表达式'''、'''后继表达式'''和'''极限表达式'''。

* '''零表达式'''指<math>n=0</math>的表达式，即空序列；
* '''后继表达式'''指<math>n>0,a_n=1</math>的表达式，即末项为1的非空序列；
* '''极限表达式'''指<math>n>0,a_n>1</math>的表达式，末项不为1的非空序列。

对于 0-Y 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，定义以下术语：

==== 行标与列标 ====
设想我们在一个无限大的矩阵下工作，从左往右是第1,2,...列，从下往上是第0,1,...行。第<math>i</math>行第<math>j</math>列的项记为<math>x_{i,j}</math>。

初始时，我们有<math>x_{0,j}=a_j</math>，<math>1\leq{j}\leq{n}</math>。

==== 父项与阶差项 ====
等于1的项没有父项。对于大于1的项<math>x_{i,j}</math>，它的父项与它位于同一行，且是满足以下条件的最右侧项<math>x_{i,k}</math>：

* <math>k<j</math>且<math>x_{i,k}<x_{i,j}</math>。
* 如果<math>i>0</math>，还要求<math>x_{i-1,k}</math>是<math>x_{i-1,j}</math>的祖先项。

这里“祖先项”的定义类似于[[Bashicu矩阵|BMS]]：一个元素自己，以及它的父项、父项的父项、父项的父项的父项......共同构成它的祖先项。

对于<math>x_{i,j}</math>，如果它有父项<math>x_{i,k}</math>，则它的阶差项为<math>x_{i+1,j}=x_{i,j}-x_{i,k}</math>；如果<math>x_{i,j}=1</math>，则它的阶差项<math>x_{i+1,j}=1</math>。

由于第<math>i</math>行的项的阶差项构成了第<math>i+1</math>行，称第<math>i+1</math>行的序列是第<math>i</math>行的序列的'''阶差序列'''。

==== 末列与坏根 ====
第<math>n</math>列称为'''末列'''。

对于末列的某一项<math>x_{i,n}</math>，它的父项设为<math>x_{i,r}</math>。如果在计算到某行(第<math>p</math>行)时有<math>x_{p,n}-x_{p,r}=1</math>，则称<math>a_r</math>为'''坏根'''，称第<math>r</math>列为'''根列'''，并且不再计算第<math>p+1</math>行及之后的行。

以上给出了 0-Y 极限表达式<math>(a_1,a_2,\cdots,a_n)</math>的完整寻找坏根流程。

== 山脉图 ==
要描述0-Y的展开规则，需要用到'''山脉图'''的辅助。对于 0-Y 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，它的山脉图的画法如下：

先按照寻找坏根的规则画出第0到<math>p</math>行。现在你有了一个<math>p\times{n}</math>的“矩阵”(第0至第<math>p</math>行，第1至第<math>n</math>列)，接下来，对于第<math>i</math>行，<math>0\leq{i}\leq{p-1}</math>进行如下操作：

对于每个<math>x_{i,j}</math>，用竖直线段连接<math>x_{i+1,j}</math>的下端与<math>x_{i,j}</math>的上端。这些竖直线段称为'''右腿'''，<math>x_{i,j}</math>称为它的端点。

对于每个大于1的<math>x_{i,j}</math>，设<math>x_{i,j}</math>有父项<math>x_{i,k}</math>，用斜线段连接<math>x_{i+1,j}</math>的下端与<math>x_{i,k}</math>的上端。这些斜线段称为'''左腿'''，<math>x_{i,k}</math>称为它的端点。

对第1到第<math>p</math>行各执行一次上述操作，就得到了<math>(a_1,a_2,\cdots,a_n)</math>的山脉图。

山脉图有以下性质：从一个有父项的元素出发，沿右腿向上走一步，再沿左腿向下走一步，就能到达它的父项。

注意：有些情况下，山脉图只包含一行，即第0行。

注：由于山脉图的某一行只和其下的项有关，你也可以在逐行往上填写阶差序列的同时画出山脉图。许多常见的0-Y教程都采用这个方法。
[[文件:0y1463797.png|缩略图]]
以<math>(1,4,6,3,7,9,7)</math>为例，其山脉图如右图所示。由于第2行末项2的阶差为1，故不再继续计算。

''(待补充附有配图的0-Y山脉图绘制例子,以及绘制0-Y山脉图的网站(有吗))''

== 展开 ==
对于 0-Y 的一个表达式<math>(a_1,a_2,\cdots,a_n)</math>：

* 如果它是零表达式，它对应序数0。
* 如果它是后继表达式，它对应<math>(a_1,a_2,\cdots,a_{n-1})</math>的后继。
* 如果它是极限表达式，它的基本列第<math>q</math>项如下确定：

# 作出<math>p\times{n}</math>的山脉图。称位于根列右侧的结构(包括阶差项和其对应的山脉图中的左右腿，不包括根列)为'''坏部'''，其余为'''好部'''。
# 删除坏部中第<math>p</math>行以下的所有项，并将<math>x_{p,n}</math>减1。
# 接下来，保留山脉图的好部不动，将坏部平移并复制在山脉图末尾，复制<math>q-1</math>次。“坏部平移”是指左右腿及端点同时平移。
# 特别地，如果某一条左腿的端点位于根列左侧，复制时左腿的端点不向右平移。
# 接下来，你得到了根列右侧的一系列山脉图和第<math>p</math>行的一系列项。从根列右侧开始，从上到下，每一行从左到右，按照以下方式填入正整数：对于某个位置，向上通过右腿移动到值为<math>x</math>的项，然后向左下通过左腿移动到值为<math>y</math>的项，则回到初始位置并填上<math>x+y</math>。
# 最后得到的第0行的序列，就是<math>(a_1,a_2,\cdots,a_n)</math>展开的基本列第<math>q-1</math>项。

0-Y的极限基本列是<math>\{(1,2),(1,3),(1,4),\cdots\}</math>，从这个基本列中元素开始取前驱或取基本列所能得到的表达式是 0-Y 的标准式。

''(待补充附有配图的0-Y展开例子,比如Y(1,4,6,4)和Y(1,4,6,3,7,9,7),后者有不平移的端点)''

== 枚举 ==
我们使用 [[Bashicu矩阵|BMS]] 对 0-Y 进行简单分析(左边是BMS，右边是0-Y)。

<math>(0)=1</math>

<math>(0)(1)=1,2</math>

<math>(0)(1)(1)=1,2,2</math>

<math>(0)(1)(2)=1,2,3</math>

<math>(0)(1)(2)(3)=1,2,3,4</math>

<math>(0)(1,1)=1,3</math>

<math>(0)(1,1)(1,0)=1,3,2</math>

<math>(0)(1,1)(1,0)(2,1)=1,3,2,4</math>

<math>(0)(1,1)(1,1)=1,3,3</math>

<math>(0)(1,1)(2,0)=1,3,4</math>

<math>(0)(1,1)(2,0)(3,1)=1,3,4,6</math>

<math>(0)(1,1)(2,1)=1,3,5</math>

<math>(0)(1,1)(2,1)(3,1)=1,3,5,7</math>

<math>(0)(1,1)(2,2)=1,3,6</math>

<math>(0)(1,1)(2,2)(3,3)=1,3,6,10</math>

<math>(0)(1,1,1)=1,4</math>

<math>(0)(1,1,1)(1,0,0)(2,1,1)=1,4,2,5</math>

<math>(0)(1,1,1)(1,1,0)=1,4,3</math>

<math>(0)(1,1,1)(1,1,0)(2,2,1)=1,4,3,7</math>

<math>(0)(1,1,1)(1,1,1)=1,4,4</math>

<math>(0)(1,1,1)(2,0,0)=1,4,5</math>

<math>(0)(1,1,1)(2,1,0)=1,4,6</math>

<math>(0)(1,1,1)(2,1,0)(1,1,1)=1,4,6,4</math>

<math>(0)(1,1,1)(2,1,0)(3,1,0)=1,4,6,8</math>

<math>(0)(1,1,1)(2,1,0)(3,2,1)=1,4,6,10</math>

<math>(0)(1,1,1)(2,1,1)=1,4,7</math>

<math>(0)(1,1,1)(2,1,1)(3,1,1)=1,4,7,10</math>

<math>(0)(1,1,1)(2,2,0)=1,4,8</math>

<math>(0)(1,1,1)(2,2,1)=1,4,9</math>

<math>(0)(1,1,1)(2,2,2)=1,4,10</math>

<math>(0)(1,1,1)(2,2,2)(3,3,3)=1,4,10,20</math>

<math>(0)(1,1,1,1)=1,5</math>

<math>(0)(1,1,1,1,1)=1,6</math>

<math>\cdots</math>

两者极限相等。

== 与[[Bashicu矩阵|BMS]]的互译 ==
事实上，0-Y与[[Bashicu矩阵|BMS]]的标准式之间有十分简单的互译关系。

对于一个 0-Y 标准表达式，作出其山脉图，但不考虑末列的影响，而是无限地逐行向上作出阶差序列，直到得到的序列全为1。

现在你有了一个<math>t\times{n}</math>的山脉图，行标为0到<math>t</math>，列标为1到<math>n</math>。

定义<math>b_{i,j}</math>如下：

* <math>x_{i,j}=1</math>时<math>b_{i,j}=0</math>。
*否则设<math>x_{i,j}</math>的父项为<math>x_{i,k}</math>，令<math>b_{i,j}=b_{i,k}+1</math>。

最后得到的矩阵<math>(b_{i,j})</math>删去最顶上全为0的行，并以水平线为轴镜像，即可得到等价的BMS。

对于一个BMS标准式<math>(d_{i,j})</math>(第1至第<math>t</math>行，第1至第<math>n</math>列)，定义<math>e_{i,j}</math>如下：

* <math>d_{i,j}=0</math>时<math>e_{i,j}=1</math>。
* 否则设<math>d_{i,j}</math>的父项为<math>d_{i,k}</math>，令<math>e_{i,j}=e_{i,k}+e_{i+1,j}</math>。如果<math>i=t</math>，我们规定<math>e_{i+1,j}=1</math>。

最后取出<math>f_k=e_{1,k}</math>，即为等价的0-Y序列。

然而，尽管目前已有的分析均支持以上结论，目前对此尚未有严格的证明。

== 与[[Y序列]]的关系 ==
0-Y虽然名字里带有'''Y'''，但它与[[Y序列]]的内核有较大差异。

历史上，0-Y的出现晚于通常的Y序列，而且强度也远低于Y序列。事实上，0-Y是仿照BMS制作出来的。

[[分类:记号]]

文件:0y1463797.png

2025-07-22T09:50:18Z

GaoKao：0-Y(1,4,6,3,7,9,7)的山脉图

== 摘要 ==
0-Y(1,4,6,3,7,9,7)的山脉图

TREE函数

2025-07-17T09:41:00Z

GaoKao：

'''TREE函数'''是由数理逻辑学家Harvey Friedman提出的图论函数。

== 定义 ==

=== 树的嵌入 ===
[[文件:树的嵌入.png|缩略图]]
给定两棵树<math>A</math>和<math>B</math>，我们称<math>A</math>能嵌入到<math>B</math>中，如果<math>B</math>能通过有限次以下操作得到<math>A</math>：

* 删除一个叶子节点。
* 若某点只有两条边和它连接，删除这个点，用一条边连接与它相邻的两个顶点(即将两条相邻的边合并成一条)。
例如，图中右边的两棵树均能嵌入到左边的树中，但它们不能互相嵌入。

=== TREE(n) ===
TREE函数研究的是一类特殊的树，其每个顶点被赋予一个值，称为该点的“颜色”。

给定正整数n，<math>\rm TREE(n)</math>被定义为满足以下条件的“树列”<math>\{T_n\}</math>的最大长度：

# 所有树的顶点至多有<math>n</math>种不同的颜色；
# <math>T_k</math>至多有<math>k</math>个顶点；
# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。

=== tree(n) ===
<math>\rm tree(n)</math>(注意大小写)被称为'''弱tree函数'''，它研究的不是染色树，而是普通树。

给定正整数n，<math>\rm tree(n)</math>被定义为满足以下条件的“树列”<math>\{T_n\}</math>的最大长度：

# <math>T_k</math>至多有<math>n+k</math>个顶点；
# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。

== 有限性证明 ==
<math>\rm TREE(n)</math>和<math>\rm tree(n)</math>的序列总是有限的，这可由Kruskal树定理保证。

我们首先要引入'''良拟序(Well-quasi-ordering)'''的概念，它可以看成[[良序]]在一般[[良序#偏序集|偏序集]]上的推广。

设<math>(X,\le)</math>为一偏序集，若对于<math>X</math>中任意无穷序列<math>x_0,x_1,x_2,\cdots</math>，总存在<math>i<j</math>使得<math>x_i\le x_j</math>，则称<math>\le</math>为集合<math>X</math>上的一个良拟序。

换句话说，若偏序集中不存在“无穷降链”，也不存在“无穷不可比较链”，则称该偏序为一个良拟序。

Kruskal树定理说明，树的嵌入关系是一个良拟序。

也就是说，任意无限棵树构成的序列中，必存在两棵树，前面的树能嵌入到后面的树中。这就证明了<math>\rm tree(n)</math>的有限性。

== 取值 ==

=== n较小时 ===
对于<math>\rm TREE(n)</math>，有：

<math>\rm TREE(1)=1</math>

<math>\rm TREE(2)=3</math>

对于<math>\rm tree(n)</math>，有：

<math>\rm tree(1)=2</math>

<math>\rm tree(2)=5</math>

<math>{\rm tree(3)>844,424,930,131,960}</math>

=== TREE(3) ===
[[文件:TREE(3).jpg|缩略图]]
和<math>\rm TREE(1)</math>、<math>\rm TREE(2)</math>仅有一位数的取值相比，<math>\rm TREE(3)</math>的值出现了“暴涨”，其远远超过了[[葛立恒数]]和[[Kirby-Paris Hydra|Hydra(5)]]，这使它成为大数领域中最著名的数字之一。

右图是<math>\rm TREE(3)</math>序列可能的前几项。

HypCos在这篇回答<ref>https://www.zhihu.com/question/353941713/answer/885942447</ref>中给出了<math>\rm TREE(3)</math>的一个下界：

\({\rm TREE(3)}>H_{\varphi(1@\omega,3)\cdot\varphi(1@\omega)}({\rm tree(tree(3)+1)})\)(其中H为[[增长层级#哈代层级|哈代层级]]，下同)

=== tree(4) ===
2025年5月24日，HypCos在这篇回答<ref>https://www.zhihu.com/question/1907086430552950742/answer/1909662327449584802</ref>中给出了<math>\rm tree(4)</math>的一个下界：<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>

== 参考资料 ==
<references />
[[分类:记号]]

文件:TREE(3).jpg

2025-07-17T08:38:15Z

GaoKao：Googology Fandom给出的TREE(3)序列的前几项。

== 摘要 ==
Googology Fandom给出的TREE(3)序列的前几项。

文件:树的嵌入.png

2025-07-15T23:35:48Z

GaoKao：解释TREE函数中两棵树的"嵌入"关系

== 摘要 ==
解释TREE函数中两棵树的"嵌入"关系

TREE函数

2025-07-15T15:20:48Z

GaoKao：/* TREE(3) */

'''TREE函数'''是由数理逻辑学家Harvey Friedman提出的图论函数。

== 定义 ==

=== 树的嵌入 ===
给定两棵树<math>A</math>和<math>B</math>，我们称<math>A</math>能嵌入到<math>B</math>中，如果<math>B</math>能通过有限次以下操作得到<math>A</math>：

* 删除一个叶子节点。
* 若某点只有两条边和它连接，删除这个点，用一条边连接与它相邻的两个顶点(即将两条相邻的边合并成一条)。

=== TREE(n) ===
给定正整数n，<math>\rm TREE(n)</math>被定义为满足以下条件的“树列”<math>\{T_n\}</math>的最大长度：

# 所有树的顶点至多有<math>n</math>种不同的颜色；
# <math>T_k</math>至多有<math>k</math>个顶点；
# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。

=== tree(n) ===
<math>\rm tree(n)</math>(注意大小写)被称为'''弱tree函数'''，它研究的不是染色树，而是普通树。

给定正整数n，<math>\rm tree(n)</math>被定义为满足以下条件的“树列”<math>\{T_n\}</math>的最大长度：

# <math>T_k</math>至多有<math>n+k</math>个顶点；
# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。

== 取值 ==

=== n较小时 ===
对于<math>\rm TREE(n)</math>，有：

<math>\rm TREE(1)=1</math>

<math>\rm TREE(2)=3</math>

对于<math>\rm tree(n)</math>，有：

<math>\rm tree(1)=2</math>

<math>\rm tree(2)=5</math>

<math>{\rm tree(3)>844,424,930,131,960}</math>

=== TREE(3) ===
和<math>\rm TREE(1)</math>、<math>\rm TREE(2)</math>仅有一位数的取值相比，<math>\rm TREE(3)</math>的值出现了“暴涨”，其远远超过了[[葛立恒数]]和[[Kirby-Paris Hydra|Hydra(5)]]，这使它成为大数领域中最著名的数字之一。

HypCos在这篇回答<ref>https://www.zhihu.com/question/353941713/answer/885942447</ref>中给出了<math>\rm TREE(3)</math>、的一个下界：

\({\rm TREE(3)}>H_{\varphi(1@\omega,3)\cdot\varphi(1@\omega)}({\rm tree(tree(3)+1)})\)(其中H为[[增长层级#哈代层级|哈代层级]]，下同)

=== tree(4) ===
2025年5月24日，HypCos在这篇回答<ref>https://www.zhihu.com/question/1907086430552950742/answer/1909662327449584802</ref>中给出了<math>\rm tree(4)</math>的一个下界：

<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>

TREE函数

2025-07-15T15:20:11Z

GaoKao：创建页面，内容为“'''TREE函数'''是由数理逻辑学家Harvey Friedman提出的图论函数。 == 定义 == === 树的嵌入 === 给定两棵树<math>A</math>和<math>B</math>，我们称<math>A</math>能嵌入到<math>B</math>中，如果<math>B</math>能通过有限次以下操作得到<math>A</math>： * 删除一个叶子节点。 * 若某点只有两条边和它连接，删除这个点，用一条边连接与它相邻的两个顶点(即将两条相邻的边合并成…”

'''TREE函数'''是由数理逻辑学家Harvey Friedman提出的图论函数。

== 定义 ==

=== 树的嵌入 ===
给定两棵树<math>A</math>和<math>B</math>，我们称<math>A</math>能嵌入到<math>B</math>中，如果<math>B</math>能通过有限次以下操作得到<math>A</math>：

* 删除一个叶子节点。
* 若某点只有两条边和它连接，删除这个点，用一条边连接与它相邻的两个顶点(即将两条相邻的边合并成一条)。

=== TREE(n) ===
给定正整数n，<math>\rm TREE(n)</math>被定义为满足以下条件的“树列”<math>\{T_n\}</math>的最大长度：

# 所有树的顶点至多有<math>n</math>种不同的颜色；
# <math>T_k</math>至多有<math>k</math>个顶点；
# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。

=== tree(n) ===
<math>\rm tree(n)</math>(注意大小写)被称为'''弱tree函数'''，它研究的不是染色树，而是普通树。

给定正整数n，<math>\rm tree(n)</math>被定义为满足以下条件的“树列”<math>\{T_n\}</math>的最大长度：

# <math>T_k</math>至多有<math>n+k</math>个顶点；
# 对于正整数<math>k<l</math>，<math>T_k</math>不能嵌入到<math>T_l</math>中。

== 取值 ==

=== n较小时 ===
对于<math>\rm TREE(n)</math>，有：

<math>\rm TREE(1)=1</math>

<math>\rm TREE(2)=3</math>

对于<math>\rm tree(n)</math>，有：

<math>\rm tree(1)=2</math>

<math>\rm tree(2)=5</math>

<math>{\rm tree(3)>844,424,930,131,960}</math>

=== TREE(3) ===
和<math>\rm TREE(1)</math>、<math>\rm TREE(2)</math>仅有一位数的取值相比，<math>\rm TREE(3)</math>的值出现了“暴涨”，其远远超过了[[葛立恒数]]和[[Kirby-Paris Hydra|Hydra(5)]]，这使它成为大数领域中最著名的数字之一。

HypCos在这篇回答<ref>https://www.zhihu.com/question/353941713/answer/885942447</ref>中给出了<math>\rm TREE(3)</math>、的一个下界：

\({\rm TREE(3)}>H_{\varphi(1\omega,3)\cdot\varphi(1\omega)}({\rm tree(tree(3)+1)})\)(其中H为[[增长层级#哈代层级|哈代层级]]，下同)

=== tree(4) ===
2025年5月24日，HypCos在这篇回答<ref>https://www.zhihu.com/question/1907086430552950742/answer/1909662327449584802</ref>中给出了<math>\rm tree(4)</math>的一个下界：

<math>{\rm tree(4)}>H_{\varepsilon_{\omega^22+1}+\alpha}(2\uparrow\uparrow\uparrow6)</math>

EBO

2025-07-14T12:50:43Z

GaoKao：创建页面，内容为“'''EBO(Extended Buchholz Ordinal, 扩展布赫兹序数)'''，是扩展BOCF的极限。 {| class="wikitable" |+EBO !记号 !表达式 |- |BOCF |<math>\psi(\Omega_{\Omega_\ddots})=\psi(I)</math> |- |MOCF |<math>\psi(\Omega_{\Omega_\ddots})=\psi(\psi_I(0))</math> |- |BMS |<math>\begin{pmatrix} 0&1&2&3&2\\ 0&1&1&1&0\\ 0&1&1&0&0 \end{pmatrix}</math> |- |0-Y |<math>1,4,7,9,5</math> |- |Y…”

'''EBO(Extended Buchholz Ordinal, 扩展布赫兹序数)'''，是扩展BOCF的极限。
{| class="wikitable"
|+EBO
!记号
!表达式
|-
|[[序数坍缩函数#BOCF|BOCF]]
|<math>\psi(\Omega_{\Omega_\ddots})=\psi(I)</math>
|-
|[[序数坍缩函数#MOCF|MOCF]]
|<math>\psi(\Omega_{\Omega_\ddots})=\psi(\psi_I(0))</math>
|-
|[[Bashicu矩阵|BMS]]
|<math>\begin{pmatrix}
0&1&2&3&2\\
0&1&1&1&0\\
0&1&1&0&0
\end{pmatrix}</math>
|-
|[[0-Y]]
|<math>1,4,7,9,5</math>
|-
|[[Y序列]]
|<math>1,2,4,8,12,15,9</math>
|-
|[[Bashicu超矩阵|BHM]]
|<math>\begin{pmatrix}
0&1&1&2&1\\
0&1&0&0&1
\end{pmatrix}</math>
|-
|[[Bashicu急矩阵|BSM]]
|<math>\begin{pmatrix}
0&1\\
0&1
\end{pmatrix}</math>
|-
|[[NOCF]]
|
|-
|[[M记号]]
|<math>\psi(\psi(M^2))</math>
|-
|[[Catching函数]]
|<math>C(\omega)</math>
|}

== 性质 ==
EBO是<math>\rm \Pi^1_1-TR_0</math>的[[证明论序数]]。

EBO是FGH和SGH的第<math>\omega</math>个追平点。

== 极限在此处的记号 ==
{| class="wikitable"
|+记号
|急序列(一行[[Bashicu急矩阵|BSM]])
|}

TFBO

2025-07-13T03:46:22Z

GaoKao：创建页面，内容为“'''TFBO(Takeuti-Feferman-Buchholz ordinal)'''，是Buchholz Hydra的极限。 {| class="wikitable" |+TFBO !记号 !表达式 |- |BOCF |<math>\psi(\Omega_{\omega+1})</math> |- |MOCF |<math>\psi(\psi_\omega(0))</math> |- |BMS |<math>\begin{pmatrix} 0&1&2&3\\ 0&1&1&2\\ 0&1&0&0 \end{pmatrix}</math> |- |0-Y |<math>1,4,6,9</math> |- |Y序列 |<math>1,2,4,8,11,15</math> |- |Bashicu…”

'''TFBO(Takeuti-Feferman-Buchholz ordinal)'''，是[[Buchholz Hydra]]的极限。
{| class="wikitable"
|+TFBO
!记号
!表达式
|-
|[[序数坍缩函数#BOCF|BOCF]]
|<math>\psi(\Omega_{\omega+1})</math>
|-
|[[序数坍缩函数#MOCF|MOCF]]
|<math>\psi(\psi_\omega(0))</math>
|-
|[[Bashicu矩阵|BMS]]
|<math>\begin{pmatrix}
0&1&2&3\\
0&1&1&2\\
0&1&0&0
\end{pmatrix}</math>
|-
|[[0-Y]]
|<math>1,4,6,9</math>
|-
|[[Y序列]]
|<math>1,2,4,8,11,15</math>
|-
|[[Bashicu超矩阵|BHM]]
|<math>\begin{pmatrix}
0&1&1&2&1&1&2&2&3&1&2&3\\
0&1&0&0&0&0&1&0&0&0&0&0
\end{pmatrix}</math>
|-
|[[BSM]]
|<math>\begin{pmatrix}
0&1&2&2&3&0&1&1&2&1&1&2
\end{pmatrix}</math>
|-
|[[M记号]]
|<math>\psi(\psi(M\times\omega+M))</math>
|}

== 性质 ==
TFBO是<math>\rm\Pi^1_1-CA+BI</math>的[[证明论序数]]。

PSS Hydra

2025-07-12T11:50:14Z

GaoKao：创建页面，内容为“'''PSS Hydra(Pair Sequence System Hydra)'''，是一种Hydra型序数记号，其行为和BO之前的BOCF类似。 == 定义 == === 合法表达式 === PSS Hydra 的表达式由<math>\psi^H_n(n\in\N)</math><ref>PSS Hydra 的定义中使用的是<math>\psi_n</math>，这里为了和OCF区分，添加了上标H。</ref>，<math>+</math>，<math>0</math>和括号组成。在使用时，<math>\psi^H_n</math>通常简写为<mat…”

'''PSS Hydra(Pair Sequence System Hydra)'''，是一种Hydra型[[序数记号]]，其行为和[[BO]]之前的[[序数坍缩函数#BOCF|BOCF]]类似。

== 定义 ==

=== 合法表达式 ===
PSS Hydra 的表达式由<math>\psi^H_n(n\in\N)</math><ref>PSS Hydra 的定义中使用的是<math>\psi_n</math>，这里为了和OCF区分，添加了上标H。</ref>，<math>+</math>，<math>0</math>和括号组成。在使用时，<math>\psi^H_n</math>通常简写为<math>pn</math>。

PSS Hydra的合法表达式可以按以下的方式递归定义：

* <math>0</math>为合法表达式，其等级为1；
* 若<math>n</math>为正整数，<math>A</math>为等级<math>\le n+1</math>的合法表达式，则<math>\psi^H_n(A)</math>为合法表达式，其等级为<math>n</math>；
* 若<math>A,B</math>分别为等级为<math>m,n</math>的合法表达式，则<math>A+B</math>也为合法表达式，其等级为<math>\max\{m,n\}</math>。

一个PSS Hydra的合法表达式对应一个小于<math>\omega^{CK}_1</math>的序数，当且仅当其等级为1。

=== 展开 ===

* 若<math>P=0</math>，则其对应序数0；
* 若<math>P=\#+\psi^H_1(0)</math>，则<math>P</math>对应一个后继序数，其前驱为<math>P'=\#</math>；
* 若<math>P=\#_1(\psi^H_k(\#_2+\psi^H_1(0)))</math>，则<math>P[n]=\#_1(\psi^H_k(\#_2)+\psi^H_k(\#_2)+\cdots+\psi^H_k(\#_2))</math>，其中<math>\psi^H_k(\#_2)</math>出现n次；
* 若<math>P=\#_1(\psi^H_k(\#_2(\psi^H_{k+1}(0))))</math>，<math>\#_2</math>不包含<math>\psi^H_k</math>，则<math>P[n]=\#_1(h^n(0))</math>，其中<math>h(x)=\psi^H_k(\#_2(x))</math>。

FSO

2025-07-10T14:10:56Z

GaoKao：修改超链接

'''FSO(Feferman-Schutte Ordinal，费福尔曼-舒特序数)'''，是[[Veblen函数#二元 Veblen 函数|veblen函数]]的极限。
{| class="wikitable"
|+FSO
!记号
!表达式
|-
|[[veblen函数]]
|<math>\varphi(1,0,0)</math>
|-
|[[OCF#BOCF|BOCF]]
|<math>\psi(\Omega^\Omega)/\psi(\psi_1(0)^{\psi_1(0)})</math>
|-
|[[OCF#MOCF|MOCF]]
|<math>\psi(\Omega^\Omega)</math>
|-
|[[BMS]]
|<math>\begin{pmatrix} 0 & 1 & 2 \\ 0 & 1 & 1 \end{pmatrix}</math>
|-
|[[HPrSS]]
|<math>1,3,5,7</math>
|-
|[[0-Y]]
|<math>1,3,5,7</math>
|-
|[[Y序列]]
|<math>1,2,4,6</math>
|-
|[[PSS Hydra]]
|<math>\psi^H_1(\psi^H_2(\psi^H_2(\psi^H_2(0))))</math>
|-
|[[weak veblen函数]]
| \(\varphi(1\text{@}(1,0))\)
|-
|[[BHM]]
|<math>\begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}</math>
|-
|[[BSM]]
|<math>\begin{pmatrix} 0 & 1 & 2 \end{pmatrix}</math>
|-
|[[NOCF]]
|<math></math>
|-
|[[M记号]]
|<math></math>
|}

== 性质 ==

== 极限在此处的记号 ==

{| class="wikitable"
|+ 记号
|}

超初等序列

2025-07-10T14:09:04Z

GaoKao：/* 与 PSS Hydra 的对应 */

'''超初等序列(Hyper Primitive Sequence System, HPrSS)'''，是一种[[Beklemishev's Worm|Worm]]型序数记号，它是[[初等序列系统|PrSS]]的一种扩展。

== 定义 ==

=== 合法表达式 ===
一个合法的 HPrSS 表达式是以 1 开头的正整数序列，即形如

<math>(a_1,a_2,\cdots,a_n)\quad(n,a_1,a_2,\cdots,a_n\in\N,a_1=1)</math>

的序列。

例如：<math>(1,4,6,4)</math>和<math>(1,1,4,5,1,4)</math>都是合法的 HPrSS 表达式，而<math>(1,2,\pi)</math>不是。

=== 结构 ===
HPrSS的合法式可分为'''零表达式'''、'''后继表达式'''和'''极限表达式'''。

* '''零表达式'''指<math>n=0</math>的表达式，即空序列；
* '''后继表达式'''指<math>n>0,a_n=1</math>的表达式，即末项为1的非空序列；
* '''极限表达式'''指<math>n>0,a_n>1</math>的表达式，末项不为1的非空序列。

对于 HPrSS 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，定义以下术语：

==== 父项 ====
对于<math>m\in\{1,2,\cdots,n\}</math>，记<math>p_m=\max\{1\le p_m<m\mid a_{p_m}<a_m\}</math>，若这样的<math>p_m</math>存在，则称<math>a_{p_m}</math>为<math>a_m</math>的'''父项'''。

如果这样的<math>p_m</math>不存在，我们也可以把<math>a_m</math>的父项定义为一个虚构的“第0项”，其值为<math>a_0=0</math>。

通俗的说，<math>a_m</math>的父项是在<math>a_m</math>左边、最靠右的、且小于<math>a_m</math>的项。

例如，在<math>(1,3,5,4,1,3)</math>中，4的父项是第一个3，而第二个1没有父项。

==== 祖先 ====
对于<math>m\in\{1,2,\cdots,n\}</math>，记<math>m_0=m</math>，<math>m_{i+1}=p_{m_i}</math>，<math>P_m=\{m_i\mid i\ge 0\}</math>我们将<math>a_m</math>的'''祖先'''定义为所有<math>a_p(p\in P_m)</math>。

通俗地说，某一项的祖先是它本身、它的父项、父项的父项、父项的父项的父项……中的某一项。

例如，<math>({\color{red}1},{\color{red}4},6,7,{\color{red}6},{\color{red}7})</math>中，末项7的祖先是所有红色的项。

==== 阶差 ====
对于<math>m\in\{1,2,\cdots,n\}</math>，若<math>a_m</math>的父项是<math>a_{p_m}</math>，则定义<math>a_m</math>的'''阶差'''为<math>d_m=a_m-a_{p_m}</math>;若没有父项，则定义<math>a_m</math>的阶差为<math>d_m=a_m</math>。

由父项的定义可知，阶差一定是正整数。

==== 阶差序列 ====
设<math>a_m</math>的阶差为<math>d_m</math>，我们把<math>(d_1,d_2,\cdots,d_n)</math>称为<math>(a_1,a_2,\cdots,a_n)</math>的'''阶差序列'''。

==== 坏根 ====
给定极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，其末项的阶差为<math>d_n</math>。我们记序列的'''坏根'''为<math>a_r</math>，其中<math>r</math>定义如下：

* 若<math>d_n=1</math>，则<math>r=p_n</math>，即序列的坏根定义末项的父项；

* 若<math>d_n\ge 1</math>，则<math>r=\max\{k\in P_n|d_k<d_n\}</math>。通俗地说，序列的坏根为末项的祖先中，最靠右的，且阶差小于末项阶差的项。

==== 序列的阶差 ====
序列的'''阶差'''定义为<math>\delta=a_n-a_r-1</math>，这一点和 [[长初等序列|LPrSS]] 一致。

==== 坏部&好部 ====
坏部、好部的定义和 PrSS 一致：坏部<math>B=(a_r,a_{r+1},\cdots,a_{n-1})</math>，好部<math>G=(a_1,a_2,\cdots,a_{r-1})</math>。

== 展开 ==
对于一个合法的 HPrSS 表达式<math>S=(a_1,a_2,\cdots,a_n)</math>，其展开规则如下：

* 若<math>S</math>为零表达式，则<math>S</math>代表序数0；
* 若<math>S</math>为后继表达式，则其前驱是'''<math>S'=(a_1,a_2,\cdots,a_{n-1})</math>'''；
* 若<math>S</math>为极限表达式，根据前文定义确定坏根、阶差、好部、坏部；记<math>B_t=(a_r+t\delta,a_{r+1}+t\delta,\cdots,a_{n-1}+t\delta)</math>，它可以看成坏部的每一项加上阶差的t倍，则其基本列的第<math>m</math>项为<math>S[m]=(G,B,B_1,B_2,\cdots,B_m)</math>。或者说，<math>S</math>的展开式为<math>(G,B,B_1,B_2,\cdots)</math>。

=== 举例 ===
考虑 HPrSS 表达式<math>(1,4,6,6)</math>。

首先，找出末项6的所有祖先项，用红色表示：<math>({\color{red}1},{\color{red}4},6,{\color{red}6})</math>。

其次，计算出阶差序列，为<math>(1,3,2,2)</math>。

然后，我们从末项的祖先项中，找到最右边的阶差小于2的项。这里4的阶差为3，我们跳过它，故坏根是首项1。

根据末项和坏根，我们得到了好部<math>G=()</math>，坏部<math>B=(1,4,6)</math>，阶差<math>\delta=6-1-1=4</math>。

根据坏部和阶差，我们可以求出<math>B_1=(5,8,10)</math>，<math>B_2=(9,12,14)</math>，等等。

最后，我们得到了展开式<math>(1,4,6,6)=(1,4,6,5,8,10,9,12,14,\cdots)</math>。

可以将其和 [[长初等序列#举例|LPrSS 中相同表达式的展开]]进行对比。

== 枚举 ==

== 与 PSS Hydra 的对应 ==
HPrSS可以和[[PSS Hydra]]存在直接的转换关系，下面介绍互译算法。

说明：算法中出现的所有“序列”均指正整数序列，不需要为HPrSS的合法式。

=== HPrSS到PSS Hydra ===
给定一个HPrSS表达式<math>S=(a_1,a_2,\cdots,a_n)</math>，设其对应的PSS Hydra表达式为<math>PH(S)</math>。则：

* 如果<math>S</math>为空序列，则<math>PH(S)=0</math>。
* 否则，记<math>x_1=1</math>，<math>x_{n+1}=\min\{k>x_n\mid a_k\le a_{x_n}\}</math>，即<math>a_{x_{n+1}}</math>是<math>a_{x_n}</math>右边第一个小于等于<math>a_{x_n}</math>的项。这样<math>S</math>就可以写成<math>(a_{x_1},S_1,a_{x_2},S_2,\cdots,a_{x_k},S_k)</math>，由<math>a_{x_{n+1}}</math>的定义可知<math>S_i</math>中的每一项均大于<math>a_{x_n}</math>。
* 我们有<math>PH(S)=\psi^H_{a_{x_1}}(PH(S_1-a_{x_1}))+\psi^H_{a_{x_2}}(PH(S_2-a_{x_2}))+\cdots+\psi^H_{a_{x_k}}(PH(S_k-a_{x_k}))</math>，其中<math>S-a</math>为将<math>S</math>的每一项都减去<math>a</math>得到的序列。

例如，考虑LPrSS表达式<math>(1,4,7,6,3,5,7)</math>

进行第二步，得到<math>k=1,x_1=1</math>，故<math>({\color{red}1},4,7,6,3,5,7)=\psi^H_1((3,6,5,2,4,6))</math>

对<math>(3,6,5,2,4,6)</math>进行第二步，得到<math>k=2,x_1=1,x_2=4</math>，故<math>({\color{red}3},6,5,{\color{red}2},4,6)=\psi^H_3((3,2))+\psi^H_2((2,4))</math>

分别计算<math>(3,2)</math>和<math>(2,4)</math>对应的PSS Hydra，得到<math>(3,2)=\psi^H_3(0)+\psi^H_2(0)</math>，<math>(2,4)=\psi^H_2(\psi^H_2(0))</math>

综上，我们得到了<math>(1,4,7,6,3,6,8)=\psi^H_1(\psi^H_3(\psi^H_3(0)+\psi^H_2(0))+\psi^H_2(\psi^H_2(\psi^H_2(0)))</math>

=== PSS Hydra到HPrSS ===
给定一个PSS Hydra表达式<math>H</math>，设其对应的HPrSS表达式为<math>LP(H)</math>。则：

* 如果<math>H=0</math>，则<math>LP(H)</math>为空序列。
* <math>LP(H_1+H_2)=(LP(H_1),LP(H_2))</math>，其中<math>(S_1,S_2)</math>为两个序列的拼接。
* <math>LP(\psi^H_x(H))=(x,(LP(H)+x))</math>。

[[分类:记号]]

超初等序列

2025-07-10T13:21:03Z

GaoKao：修改/* 举例 */ 中的一个错误

LVO

2025-07-08T06:53:08Z

GaoKao：

LVO (Large Veblen Ordinal, 大维布伦序数)，是序数元[[Veblen函数]]的极限。
{| class="wikitable"
|+LVO
!记号
!表达式
|-
|[[Veblen函数]]
|\(\varphi(1@(1,0))=\min \alpha\mapsto\varphi(1@\alpha)\;\text{Fixed Point}\)
|-
|[[序数坍缩函数#BOCF|BOCF]]/[[序数坍缩函数#MOCF|MOCF]]
|<math>\psi(\Omega^{\Omega^\Omega})</math>
|-
|[[Bashicu矩阵|BMS]]
|<math>\begin{pmatrix}
0&1&2&3&4\\
0&1&1&1&1
\end{pmatrix}
=(0,0)(1,1)(2,1)(3,1)(4,1)</math>
|-
|[[超初等序列|HPrSS]]
|<math>1,3,5,7,9</math>
|-
|[[0-Y]]
|<math>1,3,5,7,9</math>
|-
|[[Y序列]]
|<math>1,2,4,6,8,10</math>
|-
|[[PSS Hydra]]
|<math>\psi^H_1(\psi^H_2(\psi^H_2(\psi^H_2(\psi^H_2(0)))))</math>
|-
|[[BSM]]
|<math>\begin{pmatrix}
0&1&2&0&1&1&1&1&0&1&2
\end{pmatrix}</math>
|-
|[[M记号]]
|<math>\psi(\psi(M+\psi(M+\psi(M+\psi(M)))))</math>
|}

LVO

2025-07-08T06:51:53Z

GaoKao：创建页面，内容为“LVO (Large Veblen Ordinal, 大维布伦序数)，是序数元Veblen函数的极限。 {| class="wikitable" |+LVO !记号 !表达式 |- |Veblen函数 |\(\varphi(1@(1,0))=\min \alpha\mapsto\varphi(1@\alpha) Fixed Point\) |- |BOCF/MOCF |<math>\psi(\Omega^{\Omega^\Omega})</math> |- |BMS |<math>\begin{pmatrix} 0&1&2&3&4\\ 0&1&1&1&1 \end{pmatrix} =(0,0)(1,1)(2,1)(3,1)(4,1)</math> |- |…”

LVO (Large Veblen Ordinal, 大维布伦序数)，是序数元[[Veblen函数]]的极限。
{| class="wikitable"
|+LVO
!记号
!表达式
|-
|[[Veblen函数]]
|\(\varphi(1@(1,0))=\min \alpha\mapsto\varphi(1@\alpha) Fixed Point\)
|-
|[[序数坍缩函数#BOCF|BOCF]]/[[序数坍缩函数#MOCF|MOCF]]
|<math>\psi(\Omega^{\Omega^\Omega})</math>
|-
|[[Bashicu矩阵|BMS]]
|<math>\begin{pmatrix}
0&1&2&3&4\\
0&1&1&1&1
\end{pmatrix}
=(0,0)(1,1)(2,1)(3,1)(4,1)</math>
|-
|[[超初等序列|HPrSS]]
|<math>1,3,5,7,9</math>
|-
|[[0-Y]]
|<math>1,3,5,7,9</math>
|-
|[[Y序列]]
|<math>1,2,4,6,8,10</math>
|-
|[[PSS Hydra]]
|<math>\psi^H_1(\psi^H_2(\psi^H_2(\psi^H_2(\psi^H_2(0)))))</math>
|-
|[[BSM]]
|<math>\begin{pmatrix}
0&1&2&0&1&1&1&1&0&1&2
\end{pmatrix}</math>
|-
|[[M记号]]
|<math>\psi(\psi(M+\psi(M+\psi(M+\psi(M)))))</math>
|}

超初等序列

2025-07-07T14:04:29Z

GaoKao：

'''超初等序列(Hyper Primitive Sequence System, HPrSS)'''，是一种[[Beklemishev's Worm|Worm]]型序数记号，它是[[初等序列系统|PrSS]]的一种扩展。

== 定义 ==

=== 合法表达式 ===
一个合法的 HPrSS 表达式是以 1 开头的正整数序列，即形如

<math>(a_1,a_2,\cdots,a_n)\quad(n,a_1,a_2,\cdots,a_n\in\N,a_1=1)</math>

的序列。

例如：<math>(1,4,6,4)</math>和<math>(1,1,4,5,1,4)</math>都是合法的 HPrSS 表达式，而<math>(1,2,\pi)</math>不是。

=== 结构 ===
HPrSS的合法式可分为'''零表达式'''、'''后继表达式'''和'''极限表达式'''。

* '''零表达式'''指<math>n=0</math>的表达式，即空序列；
* '''后继表达式'''指<math>n>0,a_n=1</math>的表达式，即末项为1的非空序列；
* '''极限表达式'''指<math>n>0,a_n>1</math>的表达式，末项不为1的非空序列。

对于 HPrSS 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，定义以下术语：

==== 父项 ====
对于<math>m\in\{1,2,\cdots,n\}</math>，记<math>p_m=\max\{1\le p_m<m\mid a_{p_m}<a_m\}</math>，若这样的<math>p_m</math>存在，则称<math>a_{p_m}</math>为<math>a_m</math>的'''父项'''。

如果这样的<math>p_m</math>不存在，我们也可以把<math>a_m</math>的父项定义为一个虚构的“第0项”，其值为<math>a_0=0</math>。

通俗的说，<math>a_m</math>的父项是在<math>a_m</math>左边、最靠右的、且小于<math>a_m</math>的项。

例如，在<math>(1,3,5,4,1,3)</math>中，4的父项是第一个3，而第二个1没有父项。

==== 祖先 ====
对于<math>m\in\{1,2,\cdots,n\}</math>，记<math>m_0=m</math>，<math>m_{i+1}=p_{m_i}</math>，<math>P_m=\{m_i\mid i\ge 0\}</math>我们将<math>a_m</math>的'''祖先'''定义为所有<math>a_p(p\in P_m)</math>。

通俗地说，某一项的祖先是它本身、它的父项、父项的父项、父项的父项的父项……中的某一项。

例如，<math>({\color{red}1},{\color{red}4},6,7,{\color{red}6},{\color{red}7})</math>中，末项7的祖先是所有红色的项。

==== 阶差 ====
对于<math>m\in\{1,2,\cdots,n\}</math>，若<math>a_m</math>的父项是<math>a_{p_m}</math>，则定义<math>a_m</math>的'''阶差'''为<math>d_m=a_m-a_{p_m}</math>;若没有父项，则定义<math>a_m</math>的阶差为<math>d_m=a_m</math>。

由父项的定义可知，阶差一定是正整数。

==== 阶差序列 ====
设<math>a_m</math>的阶差为<math>d_m</math>，我们把<math>(d_1,d_2,\cdots,d_n)</math>称为<math>(a_1,a_2,\cdots,a_n)</math>的'''阶差序列'''。

==== 坏根 ====
给定极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，其末项的阶差为<math>d_n</math>。我们记序列的'''坏根'''为<math>a_r</math>，其中<math>r</math>定义如下：

* 若<math>d_n=1</math>，则<math>r=p_n</math>，即序列的坏根定义末项的父项；

* 若<math>d_n\ge 1</math>，则<math>r=\max\{k\in P_n|d_k<d_n\}</math>。通俗地说，序列的坏根为末项的祖先中，最靠右的，且阶差小于末项阶差的项。

==== 序列的阶差 ====
序列的'''阶差'''定义为<math>\delta=a_n-a_r-1</math>，这一点和 [[长初等序列|LPrSS]] 一致。

==== 坏部&好部 ====
坏部、好部的定义和 PrSS 一致：坏部<math>B=(a_r,a_{r+1},\cdots,a_{n-1})</math>，好部<math>G=(a_1,a_2,\cdots,a_{r-1})</math>。

== 展开 ==
对于一个合法的 HPrSS 表达式<math>S=(a_1,a_2,\cdots,a_n)</math>，其展开规则如下：

* 若<math>S</math>为零表达式，则<math>S</math>代表序数0；
* 若<math>S</math>为后继表达式，则其前驱是'''<math>S'=(a_1,a_2,\cdots,a_{n-1})</math>'''；
* 若<math>S</math>为极限表达式，根据前文定义确定坏根、阶差、好部、坏部；记<math>B_t=(a_r+t\delta,a_{r+1}+t\delta,\cdots,a_{n-1}+t\delta)</math>，它可以看成坏部的每一项加上阶差的t倍，则其基本列的第<math>m</math>项为<math>S[m]=(G,B,B_1,B_2,\cdots,B_m)</math>。或者说，<math>S</math>的展开式为<math>(G,B,B_1,B_2,\cdots)</math>。

=== 举例 ===
考虑 HPrSS 表达式<math>(1,4,6,6)</math>。

首先，找出末项6的所有祖先项，用红色表示：<math>({\color{red}1},{\color{red}4},6,{\color{red}6})</math>。

其次，计算出阶差序列，为<math>(1,2,2,2)</math>。

然后，我们从末项的祖先项中，找到最右边的阶差小于2的项。这里4的阶差为3，我们跳过它，故坏根是首项1。

根据末项和坏根，我们得到了好部<math>G=()</math>，坏部<math>B=(1,4,6)</math>，阶差<math>\delta=6-1-1=4</math>。

根据坏部和阶差，我们可以求出<math>B_1=(5,8,10)</math>，<math>B_2=(9,12,14)</math>，等等。

最后，我们得到了展开式<math>(1,4,6,6)=(1,4,6,5,8,10,9,12,14,\cdots)</math>。

可以将其和 [[长初等序列#举例|LPrSS 中相同表达式的展开]]进行对比。

== 枚举 ==

== 与 PSS Hydra 的对应 ==

HPrSS

2025-07-07T13:05:12Z

GaoKao：重定向页面至超初等序列

#重定向 [[超初等序列]]

超初等序列

2025-07-07T13:03:21Z

GaoKao：创建页面，内容为“'''超初等序列(Hyper Primitive Sequence System, HPrSS)'''，是一种Worm型序数记号，它是PrSS的一种扩展。 == 定义 == === 合法表达式 === 一个合法的 HPrSS 表达式是以 1 开头的正整数序列，即形如 <math>(s_1,s_2,\cdots,s_n)\quad(n,s_1,s_2,\cdots,s_n\in\N,s_1=1)</math> 的序列。例如：<math>(1,4,6,4)</math>和<math>(1,1,4,5,1,4)</math>都是合法的 HPrSS 表达式…”

Kirby-Paris Hydra

2025-07-06T14:58:00Z

GaoKao：/* Hydra 函数[2] */

'''Kirby-Paris Hydra(KP-Hydra)''' 是在一棵树上进行的单人游戏，需要很长时间才能终止<ref>Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic", ''Bulletin of the London Mathematical Society'' '''14''': 285–293.</ref>。由此游戏导出的函数<math>\rm{Hydra(n)}</math>的增长率超过了[[皮亚诺公理体系]]可证明停机的一切递归函数。它与[[Beklemishev's Worm|Beklemishev's worm]]密切相关。

== 规则 ==
KP-Hydra 游戏的规则如下：

* 游戏从一棵有根树T开始；
* 第n回合，选择T的一个叶子节点a，设a的父节点为b，依次执行以下操作(称为一次砍树)：
*# 删除a；
*# 若b不是根节点，取以b为根的子树T'，将其复制n次，连接到b的父节点上。
*如果某步操作后只剩下根节点，游戏结束。

我们可以用括号表示树：每一对括号表示一个节点，最外层的括号表示根节点，每个括号内层的括号表示它的子节点。

例如：设<math>n=3</math>，考虑这样的一棵树<math>(((()))(()(){\color{red}()}))</math>。

将红色的括号删除后，树的变化如下：<math>(((())){\color{blue}(()(){\color{red}()})})\rightarrow
(((())){\color{blue}(()())})\rightarrow
(((())){\color{blue}(()())}{\color{green}(()())}{\color{green}(()())}{\color{green}(()())})</math>

== 停机性证明 ==
Kirby 和 Paris 证明了以下定理：无论初始的树T怎样选取，KP-Hydra 游戏总会在有限步内终止。

其证明概要如下：

我们给每个非空树对应一个序数：

* 只含根节点的树<math>()</math>对应0;
* 若树<math>T_1,T_2,\cdots,T_n</math>分别对应序数<math>H_1,H_2,\cdots,H_n</math>（通过重新排列，不妨设<math>H_1\ge H_2\ge\cdots\ge H_n</math>），则<math>(T_1T_2\cdots T_n)</math>对应<math>\omega^{H_1}+\omega^{H_2}+\cdots+\omega^{H_n}</math>；
* 例如，<math>(((()))(()()()))
=\omega^{\omega^{\omega^0}}+\omega^{\omega^0+\omega^0+\omega^0}
=\omega^\omega+\omega^3</math>。
对树的深度归纳可知，每棵树对应的序数都小于<math>\varepsilon_0</math>。

设初始的树为<math>T</math>。我们证明：砍树操作后，树对应的序数严格减小。

* 若选取节点的父节点为根节点，则<math>T=(T_1())</math>，其对应的序数形如<math>H+1</math>，砍树操作后变为<math>H</math>，严格减小；
* 否则，设其父节点所在的子树为<math>(T_1(T_3{\color{red}()})T_2)</math>，其对应序数<math>H_1+\omega^{H_3+1}+H_2</math>。进行砍树操作后，该子树变为<math>(T_1(T_3)(T_3)\cdots(T_3)T_2)</math>，对应序数<math>H_1+\omega^{H_3}(n+1)+H_2</math>，严格减小。

假设游戏从<math>T</math>开始可以无限地进行下去，我们可以得到一系列树<math>T_1,T_2,\cdots</math>，它们对应的序数满足<math>\varepsilon_0>H_1>H_2>\cdots</math>，这与<math>\varepsilon_0</math>的良序性矛盾。故游戏总会在有限步内终止。

== Hydra 函数<ref>[https://googology.fandom.com/wiki/Kirby-Paris_hydra Kirby-Paris hydra | Googology Wiki | Fandom]</ref> ==
我们用<math>\rm{Hydra(n)}</math>表示以下特殊的 KP-Hydra 游戏终止所需要的步数：

* 初始树为含<math>n+1</math>个节点的链，即形如<math>((\cdots()\cdots))</math>的树；
*每次操作总选取最右边的节点。

下面列出<math>n</math>较小时<math>\rm{Hydra(n)}</math>的值：

<math>\rm{Hydra(0)}=0</math>

<math>\rm{Hydra(1)}=1</math>

<math>\rm{Hydra(2)}=3</math>

<math>\rm{Hydra(3)}=37</math>

<math>{\rm Hydra(4)}>f_{\omega 2+4}(5)</math>，其中<math>f</math>为[[增长层级#快速增长层级|快速增长层级]]；

<math>{\rm Hydra(5)}>f_{\omega^{\omega 2+4}}(5)</math>

一般地，记<math>\alpha_n=\omega^{\omega^{\cdots^{\omega 2+4}}}</math>，其中有<math>n-3</math>个<math>\omega</math>，则<math>f_\alpha(5)<{\rm Hydra(n)}<f_\alpha(6)</math>。因此，<math>{\rm Hydra(n)}</math>的增长率为<math>\varepsilon_0</math>。

Kirby-Paris Hydra

2025-07-06T14:53:37Z

GaoKao：

'''Kirby-Paris Hydra(KP-Hydra)''' 是在一棵树上进行的单人游戏，需要很长时间才能终止<ref>Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic", ''Bulletin of the London Mathematical Society'' '''14''': 285–293.</ref>。由此游戏导出的函数<math>\rm{Hydra(n)}</math>的增长率超过了[[皮亚诺公理体系]]可证明停机的一切递归函数。它与[[Beklemishev's Worm|Beklemishev's worm]]密切相关。

== 规则 ==
KP-Hydra 游戏的规则如下：

* 游戏从一棵有根树T开始；
* 第n回合，选择T的一个叶子节点a，设a的父节点为b，依次执行以下操作(称为一次砍树)：
*# 删除a；
*# 若b不是根节点，取以b为根的子树T'，将其复制n次，连接到b的父节点上。
*如果某步操作后只剩下根节点，游戏结束。

我们可以用括号表示树：每一对括号表示一个节点，最外层的括号表示根节点，每个括号内层的括号表示它的子节点。

例如：设<math>n=3</math>，考虑这样的一棵树<math>(((()))(()(){\color{red}()}))</math>。

将红色的括号删除后，树的变化如下：<math>(((())){\color{blue}(()(){\color{red}()})})\rightarrow
(((())){\color{blue}(()())})\rightarrow
(((())){\color{blue}(()())}{\color{green}(()())}{\color{green}(()())}{\color{green}(()())})</math>

== 停机性证明 ==
Kirby 和 Paris 证明了以下定理：无论初始的树T怎样选取，KP-Hydra 游戏总会在有限步内终止。

其证明概要如下：

我们给每个非空树对应一个序数：

* 只含根节点的树<math>()</math>对应0;
* 若树<math>T_1,T_2,\cdots,T_n</math>分别对应序数<math>H_1,H_2,\cdots,H_n</math>（通过重新排列，不妨设<math>H_1\ge H_2\ge\cdots\ge H_n</math>），则<math>(T_1T_2\cdots T_n)</math>对应<math>\omega^{H_1}+\omega^{H_2}+\cdots+\omega^{H_n}</math>；
* 例如，<math>(((()))(()()()))
=\omega^{\omega^{\omega^0}}+\omega^{\omega^0+\omega^0+\omega^0}
=\omega^\omega+\omega^3</math>。
对树的深度归纳可知，每棵树对应的序数都小于<math>\varepsilon_0</math>。

设初始的树为<math>T</math>。我们证明：砍树操作后，树对应的序数严格减小。

* 若选取节点的父节点为根节点，则<math>T=(T_1())</math>，其对应的序数形如<math>H+1</math>，砍树操作后变为<math>H</math>，严格减小；
* 否则，设其父节点所在的子树为<math>(T_1(T_3{\color{red}()})T_2)</math>，其对应序数<math>H_1+\omega^{H_3+1}+H_2</math>。进行砍树操作后，该子树变为<math>(T_1(T_3)(T_3)\cdots(T_3)T_2)</math>，对应序数<math>H_1+\omega^{H_3}(n+1)+H_2</math>，严格减小。

假设游戏从<math>T</math>开始可以无限地进行下去，我们可以得到一系列树<math>T_1,T_2,\cdots</math>，它们对应的序数满足<math>\varepsilon_0>H_1>H_2>\cdots</math>，这与<math>\varepsilon_0</math>的良序性矛盾。故游戏总会在有限步内终止。

== Hydra 函数<ref>[https://googology.fandom.com/wiki/Kirby-Paris_hydra Kirby-Paris hydra | Googology Wiki | Fandom]</ref> ==
我们用<math>\rm{Hydra(n)}</math>表示以下特殊的 KP-Hydra 游戏终止所需要的步数：

* 初始树为含<math>n</math>个节点的链，即形如<math>((\cdots()\cdots))</math>的树；
* 每次操作总选取最右边的节点。

下面列出<math>n</math>较小时<math>\rm{Hydra(n)}</math>的值：

<math>\rm{Hydra(0)}=0</math>

<math>\rm{Hydra(1)}=1</math>

<math>\rm{Hydra(2)}=3</math>

<math>\rm{Hydra(3)}=37</math>

<math>{\rm Hydra(4)}>f_{\omega 2+4}(5)</math>，其中<math>f</math>为[[增长层级#快速增长层级|快速增长层级]]；

<math>{\rm Hydra(5)}>f_{\omega^{\omega 2+4}}(5)</math>

一般地，记<math>\alpha_n=\omega^{\omega^{\cdots^{\omega 2+4}}}</math>，其中有<math>n-3</math>个<math>\omega</math>，则<math>f_\alpha(5)<{\rm Hydra(n)}<f_\alpha(6)</math>。因此，<math>{\rm Hydra(n)}</math>的增长率为<math>\varepsilon_0</math>。

Kirby-Paris Hydra

2025-07-06T14:11:34Z

GaoKao：创建页面，内容为“'''Kirby-Paris Hydra(KP-Hydra)''' 是在一棵树上进行的单人游戏，需要很长时间才能终止。由此游戏导出的函数<math>\rm{Hydra(n)}</math>的增长率超过了皮亚诺公理体系可证明停机的一切递归函数。它与Beklemishev's worm密切相关。 == 规则 == KP-Hydra 游戏的规则如下： * 游戏从一棵有根树T开始； * 第n回合，选择T的一个叶子节点a，设a的父节点为b…”

'''Kirby-Paris Hydra(KP-Hydra)''' 是在一棵树上进行的单人游戏，需要很长时间才能终止。由此游戏导出的函数<math>\rm{Hydra(n)}</math>的增长率超过了[[皮亚诺公理体系]]可证明停机的一切递归函数。它与[[Beklemishev's Worm|Beklemishev's worm]]密切相关。

== 规则 ==
KP-Hydra 游戏的规则如下：

* 游戏从一棵有根树T开始；
* 第n回合，选择T的一个叶子节点a，设a的父节点为b，依次执行以下操作(称为一次砍树)：
*# 删除a；
*# 若b不是根节点，取以b为根的子树T'，将其复制n次，连接到b的父节点上。
* 如果某步操作后只剩下根节点，游戏结束。

我们可以用括号表示树：每一对括号表示一个节点，最外层的括号表示根节点，每个括号内层的括号表示它的子节点。

例如：设<math>n=3</math>，考虑这样的一棵树<math>(((()))(()(){\color{red}()}))</math>。

将红色的括号删除后，树的变化如下：<math>(((())){\color{blue}(()(){\color{red}()})})\rightarrow
(((())){\color{blue}(()())})\rightarrow
(((())){\color{blue}(()())}{\color{green}(()())}{\color{green}(()())}{\color{green}(()())})</math>

== 停机性证明 ==
Kirby 和 Paris 证明了以下定理：无论初始的树T怎样选取，KP-Hydra 游戏总会在有限步内终止。

其证明概要如下：

我们给每一个非空树对应一个序数：

* 只含根节点的树<math>()</math>对应0;
* 若树<math>T_1,T_2,\cdots,T_n</math>分别对应序数<math>H_1,H_2,\cdots,H_n</math>，则<math>(T_1T_2\cdots T_n)</math>对应<math>\omega^{H_1}+\omega^{H_2}+\cdots+\omega^{H_n}</math>。

例如，<math>(((()))(()()()))
=\omega^{\omega^{\omega^0}}+\omega^{\omega^0+\omega^0+\omega^0}
=\omega^\omega+\omega^3</math>。

我们证明：砍树操作后，树对应的序数严格减小。

线性数阵

2025-07-05T12:52:00Z

GaoKao：

线性数阵是大部分数阵型记号的基础。

== 定义 ==

=== BEAF ===
这里以[[BEAF]]的线性数阵为例。

一个合法的 BEAF 线性数阵表达式形如<math>\{b,p,a_1,a_2,\cdots,a_n\}</math>其中<math>n</math>为非负整数，<math>b,p,a_i</math>均为正整数。

我们进行以下约定：

# 数阵的第一个数<math>b</math>称为'''底数'''；
# 数阵的第二个数<math>p</math>称为'''指数'''；
# 指数后面第一个大于1的数称为'''驾驶员'''，例如<math>\{3,2,{\color{blue}1},{\color{red}2},4\}</math>中的2，<math>\{4,{\color{blue}4},{\color{red}4},4\}</math>中红色的4；
# 驾驶员左边相邻的数称为'''副驾驶'''，例如上一条中蓝色的数。

BEAF 线性数阵的展开规则如下：

# 若没有驾驶员，则数阵的值为<math>b^p</math>；
# 若指数为1，则数阵的值为<math>b</math>；
# 否则，将驾驶员-1，副驾驶改为"整个数阵指数-1后的值"，将副驾驶左边的数全部替换为底数。例如，<math>\{4,3,{\color{blue}1},{\color{red}2}\}
=\{4,4,{\color{blue}\{4,2,1,2\}},{\color{red}1}\}
=\{4,4,\{4,4,{\color{blue}\{4,1,1,2\}},{\color{red}1}\},1\}
=\{4,4,\{4,4,4,1\},1\}</math>。

=== 改进 ===
这里介绍一种改进的线性数阵。它将经典的线性数阵改成了容易分析增长率的一元函数，将每一项的默认值改成了0，且删除了对增长率提升没有帮助的操作。

一个合法的线性数阵表达式形如<math>F(x,a_1,a_2,\cdots,a_n)</math>，其中，<math>x,n,a_i</math>均为非负整数。

我们用"#"表示任意序列，"Z"表示由若干个0组成的序列。

该线性数阵的展开规则如下：

# (基础规则)只有一项时，有<math>F(x)=x+1</math>；
# (后继规则)若第二项不为0，有<math>F(x,a+1,\#)=f^x(x)</math>，其中<math>f(x)=F(x,a,\#)</math>。例如：<math>F(3,1,4)=F(F(F(3,0,4),0,4),0,4)</math>；
# (删尾规则)若末项为0，有<math>F(\#,0)=F(\#)</math>，例如：<math>F(2,1,0)=F(2,1)</math>。
# (借位规则)否则，第二项为0且存在不为0的项。此时有<math>F(x,Z,0,a+1,\#)=F(x,Z,x,a,\#)</math>。例如：<math>F(2,0,2,5)=F(2,2,1,5)</math>。

== 增长率分析 ==
下面用[[快速增长层级]]对改进的线性数阵进行增长率分析：

<math>F(x)=F(x,0)=x+1=f_0(x)</math>

<math>F(x,1)=F^x(x)\sim f_0^x(x)=f_1(x)</math>

<math>F(x,2)\sim f_1^x(x)=f_2(x)</math>

<math>F(x,n)\sim f_n(x)</math>

<math>F(x,0,1)=F(x,x)\sim f_x(x)=f_\omega(x)</math>

<math>F(x,1,1)=F(F(\cdots,0,1),0,1)\sim f_{\omega+1}(x)</math>

<math>F(x,n,1)\sim f_{\omega+n}(x)</math>

<math>F(x,0,2)=F(x,x,1)\sim f_{\omega+x}(x)=f_{\omega\cdot 2}(x)</math>

<math>F(x,0,n)\sim f_{\omega\cdot n}(x)</math>

<math>F(x,0,0,1)=F(x,0,x)\sim f_{\omega x}(x)=f_{\omega^2}(x)</math>

<math>F(x,1,0,1)\sim f_{\omega^2+1}(x)</math>

<math>F(x,0,1,1)=F(x,x,0,1)\sim f_{\omega^2+x}(x)=f_{\omega^2+\omega}(x)</math>

<math>F(x,0,0,2)=F(x,0,x,1)\sim f_{\omega^2+\omega x}(x)=f_{\omega^22}(x)</math>

<math>F(x,0,0,0,1)=F(x,0,0,x)\sim f_{\omega^2x}(x)=f_{\omega^3}(x)</math>

<math>F(x,0,0,0,0,1)\sim f_{\omega^4}(x)</math>

<math>F(x,\underbrace{0,\cdots,0}_n,1)\sim f_{\omega^n}(x)</math>

一般来说，单独的线性数阵的极限增长率为<math>\omega^\omega</math>，但其强度会随"后继规则"的变化而变化。

例如，若把第二条规则改为<math>F(x,a+1,\#)=F(x+1,a,\#)</math>，则上述分析应该在[[哈代层级]]下进行，故极限函数的增长率相当于<math>H_{\omega^\omega}(x)\sim f_\omega(x)</math>。

Veblen 函数

2025-07-04T14:10:54Z

GaoKao：

'''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)。
[[分类:记号]]
[[分类:入门]]

线性数阵

2025-07-04T12:24:47Z

GaoKao：创建页面

线性数阵是大部分数阵型记号的基础。

== 定义 ==

Veblen 函数

2025-07-04T09:21:38Z

GaoKao：/* 序数元 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)\)。

== 枚举 ==

== 有名字的序数 ==
二元 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)。
[[分类:记号]]
[[分类:入门]]

Veblen 函数

2025-07-04T08:20:16Z

GaoKao：/* 序数元 Veblen 函数 */

Test

2025-07-04T08:00:31Z

GaoKao：

此页面为测试页面。任何人都可以随意修改此页面以便测试。

[math]G(64)=\left. \begin{matrix} 3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow}3 \\3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow}3 \\ \underbrace{\qquad \quad \vdots \qquad \quad} \\3\underbrace{\uparrow \uparrow \cdots \cdots \uparrow}3 \\3\uparrow \uparrow \uparrow \uparrow3\end{matrix} \right \} \text{64 layers}[/math]

[math]1[/math]

<math>\unicode{64}</math>

[k]

\(\alpha\text{@}\beta\)

[[[a]]]

#重定向 [[th]]

code

{| class="wikitable"
|+ 标题文本
|-
! 标题文本 !! 标题文本 !! 标题文本
|-
| 示例 || 示例 || 示例
|-
| 示例 || 示例 || 示例
|-
| 示例 || 示例 || 示例
|}

{a}

<code>我是code</code>

<pre>我是pre</pre>

<span style='background:linear-gradient(to right,#00ff00,#0000ff);-webkit-background-clip:text;-webkit-text-fill-color:transparent;'>我是美丽的span</span>

<a href='https://baidu.com'>危险的代码是不被允许的</a>

<span onclick='this.innerText="onclick是无效的！"'>click me!</span>

666

<blockquote>
我是猫娘。喵喵喵喵
</blockquote>

<blockquote>单行引言</blockquote>

<span style='background-color:red'>bgcisred</span>

[[高德纳箭头|↑]]
<iframe
src="https://expander.googology.top/index.html"
width="100%"
height="500px"
frameborder="0"
></iframe>

=== 这是一级标题 ===

==== 这是二级标题 ====

Test

2025-07-04T07:59:11Z

GaoKao：

此页面为测试页面。任何人都可以随意修改此页面以便测试。

[math]G(64)=\left. \begin{matrix} 3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow}3 \\3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow}3 \\ \underbrace{\qquad \quad \vdots \qquad \quad} \\3\underbrace{\uparrow \uparrow \cdots \cdots \uparrow}3 \\3\uparrow \uparrow \uparrow \uparrow3\end{matrix} \right \} \text{64 layers}[/math]

[math]1[/math]

<math>\unicode{64}</math>

[k]

\(\alpha\@\beta\)

[[[a]]]

#重定向 [[th]]

code

{| class="wikitable"
|+ 标题文本
|-
! 标题文本 !! 标题文本 !! 标题文本
|-
| 示例 || 示例 || 示例
|-
| 示例 || 示例 || 示例
|-
| 示例 || 示例 || 示例
|}

{a}

<code>我是code</code>

<pre>我是pre</pre>

<span style='background:linear-gradient(to right,#00ff00,#0000ff);-webkit-background-clip:text;-webkit-text-fill-color:transparent;'>我是美丽的span</span>

<a href='https://baidu.com'>危险的代码是不被允许的</a>

<span onclick='this.innerText="onclick是无效的！"'>click me!</span>

666

<blockquote>
我是猫娘。喵喵喵喵
</blockquote>

<blockquote>单行引言</blockquote>

<span style='background-color:red'>bgcisred</span>

[[高德纳箭头|↑]]
<iframe
src="https://expander.googology.top/index.html"
width="100%"
height="500px"
frameborder="0"
></iframe>

=== 这是一级标题 ===

==== 这是二级标题 ====

Veblen 函数

2025-07-04T07:54:33Z

GaoKao：添加了有限元veblen函数的定义

Veblen 函数

2025-07-03T14:56:50Z

GaoKao：添加二元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>个公共不动点.

其基本列定义如下：
# <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,\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函数 ===

=== 序数元Veblen函数 ===