ω-Y

$ω - Y$ ，是一种Worm型序数记号。

定义

合法表达式

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

$(a_{1}, a_{2}, \dots, a_{n}) (n, a_{1}, a_{2}, \dots, a_{n} \in ℕ, a_{1} = 1)$

的序列。

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

山脉图

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

行标可以说是ω-Y，以及后续可能的α-Y扩展当中，最为重要的概念，没有之一。它是各种复杂的Y系列序列的运行基础。

在ω-Y中，每一行的行标都是 $ω^{ω}$ 以下,0以上的序数。我们采用不同等级的分隔线对行标进行划分。具体地,0级分隔线（也就是什么都没有）表示它上面的行的行标等于下面的行的行标；1级分隔线（普通的单横线）表示它上面的行的行标等于下面的行的行标+ω；级分隔线（双重横线）表示它上面的行的行标等于下面的行的行标 $+ ω^{2}$ ；以此类推，n级分隔线（n重横线）表示它上面的行的行标等于下面的行的行标 $+ ω^{n}$ 。

图1是一个较为复杂的山脉图对应的行标的例子

ω-Y的山脉图中，父项、左腿、右腿、阶差等含义与0-Y、1-Y完全一致，这里不做重复介绍。

一般来说，ω-Y的山脉图具有以下特点：

不进行提取操作。提取操作的目的可以说是让“本来找不到父项的项”有机会与其它项位于同一行，从而可以找到父项。而在标准的ω-Y表达式之中，所有大于1的项都可以按规则找到父项。因此，无需进行提取。
每一列最顶端的数都是1。这个特点可以由上一条推理得到。既然每个大于1的项都存在父项，那么它和父项之间就会有阶差，而阶差位于这一项的上方。也就是说，只要一个数不是1，那么它的上面就还会有别的数字。因此，每一列最上方都是1。反过来，所有的1都一定位于所在列的顶端。这一条特点可以作为一个ω-Y山脉图是否完整的验证方式。
某一项、它的父项、以及它和父项之间的阶差项的行标关系。假设这一项的行标为β，其父项的行标为α，那么： (1) $α = β$ 时：阶差项的行标为 $β + 1$ 。也就是说，如果该项和父项位于同一行，那么阶差项在它们上面一行，中间相隔一条0级分隔线（nothing）。 (2) $α + 1 \leq β < α + ω$ 时：阶差项的行标为 $β + ω$ 。也就是说，如果该项和父项不位于同一行，但之间只有0级分隔线，那么阶差项在它们上面 $ω$ 行，中间相隔一条1级分隔线。 (3) $α + ω^{n} \leq β < α + ω^{n + 1}$ 时：阶差项的行标为 $β + ω^{n + 1}$ 。也就是说，如果该项和父项之间的分隔线等级最高为n的话，那么阶差项在它们上面 $ω^{n + 1}$ 行，中间相隔一条n+1级分隔线。

接下来是通过山脉图找到父项的方法。为了更好地解释找父项的行为，我们需要引入待定父项这一重要概念。值得一提的是，对于具备一定复杂度的记号，“通过待定父项来确定父项”几乎都成为了必不可少的一步。所以，了解这一概念以及它的相关运作方式，不止对ω-Y的理解有帮助。

具体地，对于ω-Y山脉图中的某一项（记作X），我们从X出发，沿左腿向左下走一步，然后沿右腿向上一直走到行标至多为X的行标的位置（有可能一步都走不了），最后停留的位置就是X的待定父项。

在{X, X的待定父项, X的待定父项的待定父项, ...}形成的序列中，最先遇到的数值小于X的项即为X的父项。我们算出X与其父项的阶差，根据这两项的位置按照上面的规律确定阶差项的位置，然后画出阶差项的左腿和右腿。不断对每一个新生成的项重复这一过程，直到无法这样做，最终就能得到完整的ω-Y山脉图。

网站MEGAwhY mountain可以绘制 $ω - Y$ 的山脉图。

展开

概念介绍

为了更好地介绍ω-Y的展开，我们又不得不又引入一些新的概念以及对1-Y中的概念做出一些修正：

根元素、根列：山脉图的最右列最上方元素所连接的左腿所指的元素，称为根元素。其所在的列为根列。

根列元素：位于根列的、行标小于等于根元素行标的元素，称为根列元素。

作用区域：假设所有根列元素的行标从小到大依次为 $α_{0}, α_{1}, \dots, α_{n}$ ，那么对于行标为 $α_{k}, k \leq n$ 的元素，其作用区域为根列（含）向右、行标从 $α_{k}$ （含元素，不含其下方的边）到 $α_{k + 1}$ （不含元素，含其下方的边）的区域。 $α_{n + 1}$ 被规定为山脉最右列最上方元素所在的行标。每一个根列元素都与一块作用区域一一对应，并且这些作用区域相互不重叠。

轮廓边：从一个根列元素出发，沿左腿向上一步（但不能超出这个根列元素的作用区域）之后，沿右腿向下若干步（可以不向下，但同样不能超出这个根列元素的作用区域），随后重复这个过程直到无路可走。能通过这样的操作经过的边，都是这个根列元素对应的（或者这个作用区域内的）移动边。这些边的特点是，复制时左右腿连接的对象均会移动。

非轮廓边：经过了某个作用区域，但不符合这个作用区域内轮廓边的概念的边，称为这个作用区域内的固定边。这些边的特点是，复制时左腿连接的对象保持不变。

填充边：从一个根列元素出发，沿左腿向上走一行后，沿右腿向下走一行，随后重复这个过程直到无路可走。能通过这样的操作经过的边，称为这个根列元素对应的填充边。填充边属于移动边。

行差：在本文，我们约定第 $α$ 行和第 $β$ 行（ $α \leq β$ ）的行差为满足 $α + δ = β$ 的序数 $δ$ 。例如，第 $ω$ 行和第 $ω^{2}$ 行的行差为 $ω^{2}$ ，第 $ω + 1$ 行和第 $ω \times 2 + 1$ 行的行差为 $ω + 1$ 。

一个根列元素，对应了一块作用区域、一组轮廓边和一组填充边。

展开规则

在展开ω-Y时，我们先将末列减一，然后从上到下依次处理每一个作用区域。对于每一个作用区域，我们依次进行以下操作：

轮廓边的复制：我们将轮廓边的端点及其所指的元素向右上方进行复制。具体地，向右平移（末列位置-根列位置）的列数，然后向上平移至满足以下条件的位置：若平移前端点所指的元素与根列元素行差为 $δ_{0}$ ，那么平移后对应端点所指的元素与末列最上方的元素行差也要为 $δ_{0}$ 。像这样，直至所有的轮廓边和它们所指的元素都被复制到了新的位置上。

填充边的复制:如果上一步中中，末列最上方元素与根列元素的行差为0，那么无需复制填充边，直接跳过这一步。否则，需要将轮廓边向上移动所造成的空位使用填充边进行填补。具体的做法与1-Y的填充是类似的，但从上向下进行，并且需要处理填补极限序数行时，左右脚的行差问题。

非轮廓边的复制

这些边的复制最后进行。它们的左腿指向的元素都保持不动，而右腿向右或右上平移。向右平移的列数依旧是（末列位置-根列位置）。如果这条非轮廓边右腿所指元素没有被这个作用区域内的轮廓边所指到，那么无需向上平移；如果有，那么向上平移到与末列最上方元素行差为 $δ_{0}$ 的位置。这里的 $δ_{0}$ 依旧是平移之前该元素与根列元素的行差。

重复这三步的操作（注意每次操作时末列的位置和作用区域内末列最上方元素的行标会变化），我们便能得到指定ω-Y表达式的基本列。

运算实例

ω-Y(1,3,10,29,36)的展开：首先，画出ω-Y(1,3,10,29,36)的山脉图如图2：

显然，根列是第二列，根元素为第二列第 $ω$ 行的1。因此，这个山脉图中有三个根列元素，需要划分出三个作用区域，如图3所示。

接着，我们就按照前面所说的，将末列减一之后，开始从上到下依次处理每一个区域。

对最上方作用区域的处理，首先是对轮廓边进行复制。这一区域内的所有边都是轮廓边，根列元素行标为 $ω$ ，末列最上方元素行标为 $ω + 1$ 。为了保持行差关系，我们把原来位于 $ω$ 行的元素随着复制平移到 $ω + 1, ω + 2, \dots$ 行，把原来位于 $ω + 1$ 行的元素随着复制平移到 $ω + 1, ω + 2, \dots$ 行，如图4所示：

这样一个简单的平移就完成了。注意，无论何时，作用区域内的东西都不会因为平移被移动到作用区域外。

紧接着进行填充边的复制和填充。我们找到填充边（图5深蓝色），并把它们向右和向右上填补到上一步生成的空隙中去（图5浅蓝色），就像这样：

和1-Y中的操作是一样的。毕竟，ω-Y(1,3,10,29,35)还没有超出1-Y极限。

最后是非轮廓边的复制。幸运的是，这一区域不存在非轮廓边，所以我们已经处理完成这一区域了。

对中间的作用区域的处理，还是先对轮廓边进行复制。这一个区域内，仍然所有的边都是轮廓边，根列元素行标为2，末列最上方元素行标为3，因此，我们所需要进行的平移操作和上面是一样的，找到填充边，把空隙填进去，和第一个区域一样。

第二个区域依然没有非轮廓边，那么这个区域也结束了。

最下方的区域只有一行，因此不会产生空隙，也就无需搭理填充边。所以，对它的处理也是最简单的。

ω-Y(1,4,18,48,32)的展开：首先，画出山脉图，并标出其中的根列元素、作用区域如下：

那么，依旧是把最右列减一，然后从上往下处理每一个根列元素。

对最上方作用区域的处理，这个作用区域只有一行。那么是比较简单的，向右平移就好了。

对第二个作用区域的处理，这个作用区域就有些复杂了。不过我们还是按照步骤，先找出所有的轮廓边如下：

可见，这个作用区域内的根列元素位于第 $ω$ 行，最右列的最上端元素位于第 $ω \times 2$ 行。依照相对行差进行平移，我们把原来位于 $ω$ 行的元素随着复制平移到 $ω \times 2, ω \times 3, \dots$ 行，把原来位于 $ω \times 2$ 行的元素随着复制平移到 $ω \times 3, ω \times 4, \dots$ 行，把原来位于 $ω + 1$ 行的元素随着复制平移到 $ω \times 2 + 1, ω \times 3 + 1, \dots$ 行，如图11所示。

现在，轮廓边复制完成了，轮到填充边。当空隙有多行时，填充边从上往下进行填充。但是，此时出现了一个特殊情况：我们需要把填充边复制到一个跨过了高级（ $\geq 1$ 级）分隔线的位置上。为了确保山脉图的行标规则不被破坏，我们规定：当填充边被复制到跨过了n级分隔线的位置上时，其左腿和右腿的行差需要为 $ω^{n - 1}$ 。按照这个规定，我们先填充红色部分空隙的最上面一行，这样，就多出了一个 $ω + 2$ 行。继续从上往下填充 $ω + 1$ 行和 $ω$ 行的部分，以及按照同样流程完成橙色部分的填充，结束整个填充边复制的步骤。

但是第二个区域并没有处理完。在绿色的部分，有一条大黑边与其它的部分格格不入——它是非轮廓边。我们在最后需要对它进行处理。由于它右腿所指的元素并没有被轮廓边指到，所以直接向右平移，就像这样：

第三和第四个作用区域的复制，这两个区域的边的复制没有什么特殊的行为。

于是我们完成了本例的展开。

枚举

(开摆!)

$n - Y$ 序列

$C n - Y & D n - Y$

参考资料

定义