0-Y：修订间差异

←上一编辑下一编辑→

可视化wikitext

2025年7月22日 (二) 19:54的版本

0-Y是一种Worm型序数记号，它是PrSS的一种扩展。

定义

合法表达式

一个合法的 0-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)$ 都是合法的 0-Y 表达式，而 $(1, 2, π)$ 不是。

结构

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

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

对于 0-Y 的一个极限表达式 $(a_{1}, a_{2}, \dots, a_{n})$ ，定义以下术语：

行标与列标

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

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

父项与阶差项

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

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

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

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

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

末列与坏根

第 $n$ 列称为末列。

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

以上给出了 0-Y 极限表达式 $(a_{1}, a_{2}, \dots, a_{n})$ 的完整寻找坏根流程。

山脉图

要描述0-Y的展开规则，需要用到山脉图的辅助。对于 0-Y 的一个极限表达式 $(a_{1}, a_{2}, \dots, a_{n})$ ，它的山脉图的画法如下：

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

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

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

对第1到第 $p$ 行各执行一次上述操作，就得到了 $(a_{1}, a_{2}, \dots, a_{n})$ 的山脉图。

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

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

注：由于山脉图的某一行只和其下的项有关，你也可以在逐行往上填写阶差序列的同时画出山脉图。许多常见的0-Y教程都采用这个方法。

以 $(1, 4, 6, 3, 7, 9, 7)$ 为例，其山脉图如右图所示。由于第2行末项2的阶差为1，故不再继续计算。

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

展开

对于 0-Y 的一个表达式 $(a_{1}, a_{2}, \dots, a_{n})$ ：

如果它是零表达式，它对应序数0。
如果它是后继表达式，它对应 $(a_{1}, a_{2}, \dots, a_{n - 1})$ 的后继。
如果它是极限表达式，它的基本列第 $q$ 项如下确定：

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

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

例1： $0 - Y (1, 4, 6, 4) [3]$

先作出它的山脉图，从图中可以得到：根列为第1列，坏部为第2、3、4列。

然后，将坏部第2行以下的数删除，并将其整体平移并复制2次。

接着，依次向山脉图中的“空位”填入正整数，注意所填的数满足“一个数等于其右腿和左腿连接的数之差”。

最后，根据山脉图的第0行，我们得到了 $0 - Y (1, 4, 6, 4) [3] = 0 - Y (1, 4, 6, 3, 7, 10, 6, 11, 15, 10)$ 。

例2： $0 - Y (1, 4, 6, 3, 7, 9, 7) [3]$

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

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

复制、填充后得到的山脉图如下。

因此 $0 - Y (1, 4, 6, 3, 7, 9, 7) [3] = 0 - Y (1, 4, 6, 3, 7, 9, 6, 11, 13, 10, 16, 18, 15)$

枚举

我们使用 BMS 对 0-Y 进行简单分析(左边是BMS，右边是0-Y)。

$(0) = 1$

$(0) (1) = 1, 2$

$(0) (1) (1) = 1, 2, 2$

$(0) (1) (2) = 1, 2, 3$

$(0) (1) (2) (3) = 1, 2, 3, 4$

$(0) (1, 1) = 1, 3$

$(0) (1, 1) (1, 0) = 1, 3, 2$

$(0) (1, 1) (1, 0) (2, 1) = 1, 3, 2, 4$

$(0) (1, 1) (1, 1) = 1, 3, 3$

$(0) (1, 1) (2, 0) = 1, 3, 4$

$(0) (1, 1) (2, 0) (3, 1) = 1, 3, 4, 6$

$(0) (1, 1) (2, 1) = 1, 3, 5$

$(0) (1, 1) (2, 1) (3, 1) = 1, 3, 5, 7$

$(0) (1, 1) (2, 2) = 1, 3, 6$

$(0) (1, 1) (2, 2) (3, 3) = 1, 3, 6, 10$

$(0) (1, 1, 1) = 1, 4$

$(0) (1, 1, 1) (1, 0, 0) (2, 1, 1) = 1, 4, 2, 5$

$(0) (1, 1, 1) (1, 1, 0) = 1, 4, 3$

$(0) (1, 1, 1) (1, 1, 0) (2, 2, 1) = 1, 4, 3, 7$

$(0) (1, 1, 1) (1, 1, 1) = 1, 4, 4$

$(0) (1, 1, 1) (2, 0, 0) = 1, 4, 5$

$(0) (1, 1, 1) (2, 1, 0) = 1, 4, 6$

$(0) (1, 1, 1) (2, 1, 0) (1, 1, 1) = 1, 4, 6, 4$

$(0) (1, 1, 1) (2, 1, 0) (3, 1, 0) = 1, 4, 6, 8$

$(0) (1, 1, 1) (2, 1, 0) (3, 2, 1) = 1, 4, 6, 10$

$(0) (1, 1, 1) (2, 1, 1) = 1, 4, 7$

$(0) (1, 1, 1) (2, 1, 1) (3, 1, 1) = 1, 4, 7, 10$

$(0) (1, 1, 1) (2, 2, 0) = 1, 4, 8$

$(0) (1, 1, 1) (2, 2, 1) = 1, 4, 9$

$(0) (1, 1, 1) (2, 2, 2) = 1, 4, 10$

$(0) (1, 1, 1) (2, 2, 2) (3, 3, 3) = 1, 4, 10, 20$

$(0) (1, 1, 1, 1) = 1, 5$

$(0) (1, 1, 1, 1, 1) = 1, 6$

$\dots$

两者极限相等。

与BMS的互译

事实上，0-Y与BMS的标准式之间有十分简单的互译关系。

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

现在你有了一个 $t \times n$ 的山脉图，行标为0到 $t$ ，列标为1到 $n$ 。

定义 $b_{i, j}$ 如下：

$x_{i, j} = 1$ 时 $b_{i, j} = 0$ 。
否则设 $x_{i, j}$ 的父项为 $x_{i, k}$ ，令 $b_{i, j} = b_{i, k} + 1$ 。

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

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

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

最后取出 $f_{k} = e_{1, k}$ ，即为等价的0-Y序列。

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

与Y序列的关系

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

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

@@ 第64行： / 第64行： @@
 以<math>(1,4,6,3,7,9,7)</math>为例，其山脉图如右图所示。由于第2行末项2的阶差为1，故不再继续计算。
-''(待补充附有配图的0-Y山脉图绘制例子,以及绘制0-Y山脉图的网站(有吗))''
+''(待补充绘制0-Y山脉图的网站(有吗))''
 == 展开 ==
@@ 第82行： / 第82行： @@
 -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),后者有不平移的端点)''
+例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>
 == 枚举 ==