Y序列

Y序列，一般指1-Y，一种Worm型序数记号。

定义

合法表达式

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

$(a_1,a_2,\cdots ,a_n)(n,a_1,a_2,\cdots ,a_n\in \mathbb{\mathbb{N}},a_1=1)$

的序列。

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

结构

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

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

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

行标与列标

设想我们在一个无限大的矩阵下工作，从左往右是第1,2,...列，从下往上是第0,1,...行。与0-Y不同的是：

• 行标现在可以是一个超限序数，例如第$\omega$行。
• 一些项现在可以不赋予任何数作为取值，这些项称为空项，记作$\varnothing$。

第$\alpha$行第$j$列的项记为$x_{\alpha ,j}$。

初始时，我们有$x_{0,j}=a_j$，$1\le j\le n$。

后继序数行的父项 & 阶差项

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

• $k<j$且$x_{\alpha +1,k}<x_{\alpha +1,j}$。
• $x_{\alpha ,k}$是$x_{\alpha ,j}$的祖先项。

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

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

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

对于任何序数$\alpha$，项$x_{\alpha ,j}$：

• 如果它有父项$x_{\alpha ,k}$，则它的阶差项为$x_{\alpha +1,j}=x_{\alpha ,j}-x_{\alpha ,k}$。
• 如果它没有父项，或者为空项，它的阶差项为$x_{\alpha ,j}=\varnothing$。

由于第$\alpha$行的项的阶差项构成了第$\alpha +1$行，称第$\alpha +1$行的序列是第$\alpha$行的序列的阶差序列。

极限序数行的父项 & 提取

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

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

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

对大于1的项$x_{\alpha ,j}$定义如下概念：

1. 设$x_{\alpha ,j}=x_{\beta +p,j}$，令$a=j$。
2. 设$x_{\beta +p-1,a}$的父项为$x_{\beta +p-1,k}$。如果$x_{\beta +p-1,k}$是主项，或者$x_{\beta +p,k}$是主项，称$x_{\alpha ,k}$是$x_{\alpha ,j}$的拟父项。
3. 否则令$a=k$并回到第2步，直到找到某个主项，设其列标是$l$，称$x_{\alpha ,l}$是$x_{\alpha ,j}$的拟父项。

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

• $k<j$且$x_{\alpha ,k}<x_{\alpha ,j}$。
• $x_{\alpha ,k}$是$x_{\alpha ,j}$的拟祖先项。

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

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

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

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

末列与坏根

第$n$列称为末列。

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

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

山脉图

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

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

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

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

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

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

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

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

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

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

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

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

网站whY mountain可以绘制1-Y的山脉图。

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

展开

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

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

先作出其山脉图，求出根列$r$，根列右侧的结构称为坏部。

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

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

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

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

第$k(1\le k\le m)$层山脉图的展开需要引入几个概念：顶点元素、平移边、轮廓边、参考边。

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

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

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

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

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

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

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

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

枚举

(开摆!)

n-Y序列

通过某种方式，我们可以把1-Y前面的参数1扩展到任意大的自然数$n$。详细信息请参考ω-Y页面。