Y序列：修订间差异

←上一编辑下一编辑→

可视化wikitext

2025年7月29日 (二) 10:50的版本

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

定义

合法表达式

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

结构

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

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

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

行标与列标

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

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

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

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

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

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

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

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

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

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

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

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

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

极限序数行的父项 & 提取

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

设极限序数 $α = β + ω < ω^{2}$ ， $β$ 为极限序数。则定义项 $x_{α, j}$ 如下：

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

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

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

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

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

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

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

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

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

末列与坏根

第 $n$ 列称为末列。

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

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

山脉图

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

$1 - Y$ 的山脉图作图难度略高于0-Y。对于 $1 - Y$ 的一个极限表达式 $(a_{1}, a_{2}, \dots, a_{n})$ ，它的山脉图的画法如下：

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

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

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

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

接下来，对于第极限序数 $α = β + ω$ 行，进行如下操作：

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

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

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

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

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

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

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

展开

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

对于 $1 - Y$ 的极限表达式 $Y (a_{1}, a_{2}, \dots, a_{n})$ ，其基本列第 $q$ 项可按以下方式确定：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

枚举

(开摆!)

$n - Y$ 序列

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

参考资料

↑ Suzuka梅天狸：Y序列专题(4)——让我们请出主角登场(下) ，https://zhuanlan.zhihu.com/p/671375564

[1] Suzuka梅天狸：Y序列专题(4)——让我们请出主角登场(下) ，https://zhuanlan.zhihu.com/p/671375564

[1]

@@ 第1行： / 第1行： @@
-'''Y序列'''，一般指'''1-Y'''，一种[[Beklemishev's Worm|Worm]]型序数记号。
+'''<math>\mathrm{Y}</math>序列'''，一般指<math>\mathrm{1-Y}</math>，一种[[Beklemishev's Worm|Worm]]型序数记号。
 == 定义 ==
 === 合法表达式 ===
-一个合法的 1-Y 表达式是以 1 开头的正整数序列，即形如
+一个合法的 <math>\mathrm{1-Y}</math> 表达式是以 1 开头的正整数序列，即形如
 <math>(a_1,a_2,\cdots,a_n)\quad(n,a_1,a_2,\cdots,a_n\in\N,a_1=1)</math>
@@ 第10行： / 第10行： @@
 的序列。
-例如：<math>(1,4,6,4)</math>和<math>(1,1,4,5,1,4)</math>都是合法的 1-Y 表达式，而<math>(1,2,\pi)</math>不是。
+例如：<math>(1,4,6,4)</math>和<math>(1,1,4,5,1,4)</math>都是合法的 <math>\mathrm{1-Y}</math> 表达式，而<math>(1,2,\pi)</math>不是。
 ===  结构 ===
--Y的合法表达式可分为'''零表达式'''、'''后继表达式'''和'''极限表达式'''。
+<math>\mathrm{1-Y}</math> 的合法表达式可分为'''零表达式'''、'''后继表达式'''和'''极限表达式'''。
 * '''零表达式'''指<math>n=0</math>的表达式，即空序列；
@@ 第19行： / 第19行： @@
 * '''极限表达式'''指<math>n>0,a_n>1</math>的表达式，末项不为1的非空序列。
-对于 1-Y 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，定义以下术语：
+对于 <math>\mathrm{1-Y}</math> 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，定义以下术语：
 ==== 行标与列标 ====
-设想我们在一个无限大的矩阵下工作，从左往右是第1,2,...列，从下往上是第0,1,...行。'''与0-Y不同的是：
+设想我们在一个无限大的矩阵下工作，从左往右是第1,2,...列，从下往上是第0,1,...行。'''与 <math>\mathrm{0-Y}</math> 不同的是：
 * 行标现在可以是一个超限序数，例如第<math>\omega</math>行。
 * 一些项现在可以不赋予任何数作为取值，这些项称为空项，记作<math>\varnothing</math>。'''
@@ 第77行： / 第77行： @@
 对于末列的某一项<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>的完整寻找坏根流程。
+以上给出了 <math>\mathrm{1-Y}</math> 极限表达式<math>(a_1,a_2,\cdots,a_n)</math>的完整寻找坏根流程。
 == 山脉图 ==
-要描述1-Y的展开规则或者直观理解部分定义，需要用到'''山脉图'''的辅助。
+要描述 <math>\mathrm{1-Y}</math> 的展开规则或者直观理解部分定义，需要用到'''山脉图'''的辅助。
--Y的山脉图作图难度略高于[[0-Y]]。对于 1-Y 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，它的山脉图的画法如下：
+<math>\mathrm{1-Y}</math> 的山脉图作图难度略高于[[0-Y]]。对于 <math>\mathrm{1-Y}</math> 的一个极限表达式<math>(a_1,a_2,\cdots,a_n)</math>，它的山脉图的画法如下：
 先按照寻找坏根的规则逐行向上求出各项，直到某次提取的所有主项全为1，不进行这次提取。
@@ 第100行： / 第100行： @@
 注意：有些情况下，山脉图只包含一行，即第0行。
--Y的山脉图中，从一个有父项的项出发，沿右腿向上走一步，再沿左腿向下走一步，就能到达它的父项。
+<math>\mathrm{1-Y}</math> 的山脉图中，从一个有父项的项出发，沿右腿向上走一步，再沿左腿向下走一步，就能到达它的父项。
 对于极限序数<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的山脉图。
+网站[https://naruyoko.github.io/whYmountain/ whY mountain]可以绘制 <math>\mathrm{1-Y}</math> 的山脉图。
 ''(待补充附有配图的1-Y山脉图绘制例子,以及绘制1-Y山脉图的网站(有吗),以及极限序数行父项关系的直观理解)''
 == 展开 ==
--Y的展开难度远高于[[0-Y]]。
+<math>\mathrm{1-Y}</math> 的展开难度远高于[[0-Y]]。
-对于1-Y的极限表达式<math>\mathrm{Y}(a_1,a_2,\cdots,a_n)</math>，其基本列第<math>q</math>项可按以下方式确定：
+对于 <math>\mathrm{1-Y}</math> 的极限表达式<math>\mathrm{Y}(a_1,a_2,\cdots,a_n)</math>，其基本列第<math>q</math>项可按以下方式确定：
 先作出其山脉图，求出根列<math>r</math>，根列右侧的结构称为'''坏部'''。
@@ 第117行： / 第117行： @@
 设序列一共进行了<math>m</math>次提取操作，此时山脉图被分为<math>m+1</math>层，第<math>k</math>层的行标位于<math>\omega(k-1)</math>和<math>\omega k</math>之间。
--Y的展开是从上到下逐层进行的。
+<math>\mathrm{1-Y}</math> 的展开是从上到下逐层进行的。
-对于最上面一层，其展开规则和0-Y类似：
+对于最上面一层，其展开规则和 <math>\mathrm{0-Y}</math> 类似：
 # 先将末列行标第二大的项<math>x_{\omega m+p,n}</math>减1(行标最大的项为1)，删除本层坏部第<math>\omega m+p</math>行以下元素的数值。
@@ 第136行： / 第136行： @@
 * '''参考边'''：从本层根列的主项出发，得到的所有轮廓边称为参考边。取基本列第<math>q</math>项时，根列右边的结构需要循环复制<math>q-1</math>次。在每一轮复制的过程中，三种边的行为如下：
-* 平移边只需要简单地向右平移。特别地，若左腿的端点位于根列左侧，则左腿的端点保持不动。这一点和0-Y的规则类似。
+* 平移边只需要简单地向右平移。特别地，若左腿的端点位于根列左侧，则左腿的端点保持不动。这一点和 <math>\mathrm{0-Y}</math> 的规则类似。
 * 轮廓边在向右平移的同时，还需要向上提升它的高度。具体来说，提升的高度为最右列和根列顶点元素的高度差。
 * 参考边在向右平移后，还要向上复制，用来填补平移边和轮廓边之间的空隙。
@@ 第151行： / 第151行： @@
 ''(开摆!)''
-== n-Y序列 ==
+== <math>\mathrm{n-Y}</math>序列 ==
-通过某种方式，我们可以把1-Y前面的参数1扩展到任意大的自然数<math>n</math>。详细信息请参考[[ω-Y]]页面。
+通过某种方式，我们可以把 <math>\mathrm{1-Y}</math> 前面的参数1扩展到任意大的自然数<math>n</math>。详细信息请参考[[ω-Y]]页面。
 == 参考资料 ==
 [[分类:记号]]