初等序列系统：修订间差异

←上一编辑下一编辑→

可视化wikitext

2025年7月27日 (日) 16:05的版本

PrSS 虽然结构简单，但是却是目前已知的最强大的递归核心的基础．^[1]
~~------~~ 曹知秋

初等序列系统（Primative Sequence System, PrSS）是一种 Worm 型序数记号。

定义

合法式

一个合法的 PrSS 表达式是形如 $S = (s_{1}, s_{2}, \dots, s_{n}) | n, s_{1}, s_{2}, \dots, s_{n} \in ℕ$

且满足 $s_{1} = 0, s_{k + 1} - s_{k} ⩽ 1 (k = 1, 2, \dots n - 1)$ 的自然数列^{[注 1]}（特别地，空序列 $()$ 是合法的 PrSS 表达式）

例：

$(0, 1, 1, 2, 2)$ 是一个合法的 PrSS 表达式
$(Ω, 1, 2)$ 不是一个合法的 PrSS 表达式，因为 $Ω \notin ℕ$
$(0, 2, 4, 6, 8)$ 不是一个合法的 PrSS 表达式，因为不满足条件 $s_{k + 1} - s_{k} ⩽ 1$

结构

合法的 PrSS 表达式可以分为零表达式、后继表达式、极限表达式，其定义如下：

零表达式：满足 $n = 0$ 的表达式，即空序列 $()$
后继表达式：满足 $n > 0$ 且 $s_{n} = 0$ 的表达式，例如 $(0, 1, 2, 0)$
极限表达式：满足 $n > 0$ 且 $s_{n} > 0$ 的表达式，例如 $(0, 1, 2, 1)$

一个 PrSS 的极限表达式由以下四个部分组成：

末项（Last Term）
坏部（Bad Part）
坏根（Bad Root）
好部（Good Part）

末项

对于最大下标为 $n$ 的 PrSS 表达式 $S = (s_{1}, s_{2}, \dots, s_{n})$ ，其末项 $L = s_{n}$ ，即 $S = (s_{1}, s_{2}, \dots, L)$

坏根

对于 $S = (s_{1}, s_{2}, \dots, s_{n}) | L = s_{n}$ ，令 $k = \max {1 \leq k < n | s_{k} < s_{n}}$ ，那么坏根定义为 $r = s_{k}$ ，即 $S = (s_{1}, s_{2}, \dots, r, \dots, L)$

通俗的说，是最靠右的小于末项的项。

因为极限表达式满足 $L = s_{n} > 0$ 且 $s_{1} = 0$ ，所以坏根总是存在的。

坏部

对于 $S = (s_{1}, s_{2}, \dots, s_{k}, \dots, s_{n}) | L = s_{n}, r = s_{k}$ ，坏部定义为 $B = (s_{k}, s_{k + 1}, \dots, s_{n - 1})$ ，即 $S = (s_{1}, s_{2}, \dots, s_{k - 1}, B, L)$

通俗地说，是坏根（含）到末项（不含）的部分。坏部最短为 1 项。

好部

对于 $S = (s_{1}, s_{2}, \dots, s_{k}, \dots, s_{n}) | L = s_{n}, r = s_{k}$ ，好部定义为 $G = (s_{1}, s_{2}, \dots, s_{k - 1})$ ，即 $S = (G, B, L)$

通俗地说，好部是坏部之前的部分。好部可以为空。

展开

PrSS 的良序性已经得到证明，且其标准式的序等价于字典序，因此所有标准的 PrSS 表达式都一一对应着一个序数．

对于一个合法的 PrSS 表达式 $S = (s_{1}, s_{2}, \dots, s_{n - 1}, s_{n})$ ，其展开规则如下：

如果 $S$ 是零表达式，则 $S$ 代表序数 $0$
如果 $S$ 是后继表达式，则其前驱是 $S^{'} = (s_{1}, s_{2}, \dots, s_{n - 1})$
如果 $S$ 是极限表达式，则根据前文定义确定好部、坏部，得到 $S = (G, B, L)$ . 则其基本列的第 $m$ 项定义为 $S [m] = (G, \underset{m}{\underset{⏟}{B, B, B, \dots, B}})$ ，其中 $m \in ℕ$ . 或者说 $S$ 的展开式为 $(G, \underset{ω}{\underset{⏟}{B, B, B, \dots}})$

举例：

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

末项是标绿的 $3$ ，坏根是从右往左数第一个比 $3$ 小的数，也就是标红色的 $2$ 。

接下来，根据坏部的定义可以知道坏部是 $(2, 3, 3)$ 。

坏根之前的好部不用管，将末项抛弃：

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

复制坏部：

$S = (0, 1, 2, 3, 3, 2, 3, 3, 2, 3, 3, \dots)$

我们就成功地展开了一个 PrSS 表达式。

与康托范式的对应

参见词条 PrSS VS 康托范式。

拓展

PrSS 记号有两种拓展：

高维 PrSS，如 PrSS 原作者所创的 BMS
阶差 PrSS ，有两种形式：
- LPrSS 及各种 Hydra 记号
- HPrSS，0-Y，Y序列等复杂阶差型记号

它们以 PrSS 序列为基础，刻画了非常巨大的序数。

历史

在 2014.8.14，Bashicu 首次提出并使用 Basic 语言定义了 PrSS。^[2]

脚注

↑ 实际上，以 1 序列开头的 PrSS 也是被广为接受的，其更多被用于表示阶差型序列．但无论 0 或 1 为开头，均不影响 PrSS 的展开方式与极限．

参考资料

↑ 曹知秋. 大数理论: Vol.1[EB/OL]. (2025-05-16) [2025-07-02]: 53-54. https://github.com/ZhiqiuCao/Googology
↑ Bashicu. basic言語で巨大数を作ってみたので上げてみる[EB/OL]. 2014, 08/14:109. https://gyafun.jp/ln/archive/ln10.html

[2] 实际上，以 1 序列开头的 PrSS 也是被广为接受的，其更多被用于表示阶差型序列．但无论 0 或 1 为开头，均不影响 PrSS 的展开方式与极限．

[1] 曹知秋. 大数理论: Vol.1[EB/OL]. (2025-05-16) [2025-07-02]: 53-54. https://github.com/ZhiqiuCao/Googology

[3] Bashicu. basic言語で巨大数を作ってみたので上げてみる[EB/OL]. 2014, 08/14:109. https://gyafun.jp/ln/archive/ln10.html

[1]

[注 1]

[2]

@@ 第1行： / 第1行： @@
 <div style="word-wrap: break-word;text-wrap: pretty;color: var(--color-subtle);font-style: italic;width:Fit-content;padding:1rem 1rem 2rem 1rem;border-left:solid #00000030 5px;background-color:var(--color-surface-2)">PrSS 虽然结构简单，但是却是目前已知的最强大的递归核心的基础．<ref>曹知秋. 大数理论: Vol.1[EB/OL]. (2025-05-16) [2025-07-02]: 53-54. https://github.com/ZhiqiuCao/Googology</ref><br /><span style='float:right'><del>------</del> 曹知秋</span></div>
-'''初等序列系统（Primative Sequence System, PrSS）'''是一种 [[Beklemishev's Worm|Worm]] 型[[序数记号]]．
+'''初等序列系统（Primative Sequence System, PrSS）'''是一种 [[Beklemishev's Worm|Worm]] 型[[序数记号]]。
 == 定义 ==
 === 合法式 ===
-一个'''合法'''的 PrSS 表达式是形如
+一个'''合法'''的 PrSS 表达式是形如 <math>S=(s_{1},s_{2},\cdots,s_{n})|n,s_{1},s_{2},\cdots,s_{n}\in\mathbb{N}</math>
- <math>S=(s_{1},s_{2},\cdots,s_{n})|n,s_{1},s_{2},\cdots,s_{n}\in\mathbb{N}</math>
+且满足 <math>s_1=0,s_{k+1}-s_k\leqslant1(k=1,2,\cdots n-1)</math> 的自然数列<ref group="注">实际上，以 1 序列开头的 PrSS 也是被广为接受的，其更多被用于表示阶差型序列．但无论 0 或 1 为开头，均不影响 PrSS 的展开方式与极限．</ref>（特别地，空序列 <math>()</math> 是合法的 PrSS 表达式）
-且满足以下条件的自然数列：
-<math>\langle \text{1} \rangle\ \quad s_{1}=0\quad\text{if }n>0.</math><ref group="注">实际上，以 1 序列开头的 PrSS 也是被广为接受的，其更多被用于表示阶差型序列．但无论 0 或 1 为开头，均不影响 PrSS 的展开方式与极限．</ref>
-<math>\langle \text{2} \rangle\ \quad s_{k+1}-s_{k}\leq 1\quad\forall k\in\{1,2\cdots,n-1\}.</math>
 '''例：'''
-<math>(0,1,1,2,2)</math> 是一个合法的 PrSS 表达式.
+* <math>(0,1,1,2,2)</math> 是一个合法的 PrSS 表达式
+* <math>(\Omega,1,2)</math> 不是一个合法的 PrSS 表达式，因为 <math>\Omega\notin\mathbb{N}</math>
-<math>(\Omega,1,2)</math> 不是一个合法的 PrSS 表达式，因为 <math>\Omega\notin\mathbb{N}</math>.
+* <math>(0,2,4,6,8)</math> 不是一个合法的 PrSS 表达式，因为不满足条件 <math>s_{k+1}-s_k\leqslant1</math>
-<math>(0,2,4,6,8)</math> 不是一个合法的 PrSS 表达式，因为不满足条件 <math>\langle \text{2} \rangle</math>.
 === 结构 ===
 合法的 PrSS 表达式可以分为零表达式、后继表达式、极限表达式，其定义如下：
-*'''零表达式'''：满足 <math>n=0</math> 的表达式，即空序列 <math>()</math>.
+*'''零表达式'''：满足 <math>n=0</math> 的表达式，即空序列 <math>()</math>
-*'''后继表达式'''：满足 <math>n>0</math> 且 <math>s_{n}=0</math> 的表达式，例如 <math>(0,1,2,0)</math>.
+*'''后继表达式'''：满足 <math>n>0</math> 且 <math>s_{n}=0</math> 的表达式，例如 <math>(0,1,2,0)</math>
-*'''极限表达式'''：满足 <math>n>0</math> 且 <math>s_{n}>0</math> 的表达式，例如 <math>(0,1,2,1)</math>.
+*'''极限表达式'''：满足 <math>n>0</math> 且 <math>s_{n}>0</math> 的表达式，例如 <math>(0,1,2,1)</math>
 一个 PrSS 的'''极限表达式'''由以下四个部分组成：
-# 末项 <math>\mathrm{(Last\ Term)}</math>.
-# 坏部 <math>\mathrm{(Bad\ Part)}</math>.
+# 末项（Last Term）
-# 坏根 <math>\mathrm{(Bad\ Root)}</math>.
+# 坏部（Bad Part）
-# 好部 <math>\mathrm{(Good\ Part)}</math>.
+# 坏根（Bad Root）
+# 好部（Good Part）
 ==== 末项 ====
-对于最大下标为 <math>n</math> 的 PrSS 表达式 <math>S=(s_{1},s_{2},\cdots,s_{n})</math>，其末项 <math>L=s_{n}</math>，即
+对于最大下标为 <math>n</math> 的 PrSS 表达式 <math>S=(s_{1},s_{2},\cdots,s_{n})</math>，其末项 <math>L=s_{n}</math>，即 <math>S=(s_{1},s_{2},\cdots,L)</math>
- <math>S=(s_{1},s_{2},\cdots,L).</math>
 ==== 坏根 ====
-对于 <math>S=(s_{1},s_{2},\cdots,s_{n})|L=s_{n}</math>，令 <math>k=\max\{1 \leq k < n|s_{k}<s_{n}\}</math>，那么坏根定义为 <math>r=s_{k}</math>，即
+对于 <math>S=(s_{1},s_{2},\cdots,s_{n})|L=s_{n}</math>，令 <math>k=\max\{1 \leq k < n|s_{k}<s_{n}\}</math>，那么坏根定义为 <math>r=s_{k}</math>，即 <math>S=(s_{1},s_{2},\cdots,r,\cdots,L)</math>
- <math>S=(s_{1},s_{2},\cdots,r,\cdots,L).</math>
+通俗的说，是最靠右的小于末项的项。
-通俗的说，是最靠右的小于末项的项．
-因为极限表达式满足 <math>L=s_n>0</math> 且 <math>s_1=0</math>，所以坏根总是存在的．
+因为极限表达式满足 <math>L=s_n>0</math> 且 <math>s_1=0</math>，所以坏根总是存在的。
 ==== 坏部 ====
-对于 <math>S=(s_{1},s_{2},\cdots,s_{k},\cdots,s_{n})|L=s_{n},r=s_{k}</math>，坏部定义为 <math>B=(s_{k},s_{k+1},\cdots,s_{n-1})</math>，即
+对于 <math>S=(s_{1},s_{2},\cdots,s_{k},\cdots,s_{n})|L=s_{n},r=s_{k}</math>，坏部定义为 <math>B=(s_{k},s_{k+1},\cdots,s_{n-1})</math>，即 <math>S=(s_{1},s_{2},\cdots,s_{k-1},B,L)</math>
- <math>S=(s_{1},s_{2},\cdots,s_{k-1},B,L)</math>
+通俗地说，是坏根（含）到末项（不含）的部分。坏部最短为 1 项。
-通俗地说，是坏根(含)到末项(不含)的部分．坏部最短为 1 项．
 ==== 好部 ====
-对于 <math>S=(s_{1},s_{2},\cdots,s_{k},\cdots,s_{n})|L=s_{n},r=s_{k}</math>，好部定义为 <math>G=(s_{1},s_{2},\cdots,s_{k-1})</math>，即
+对于 <math>S=(s_{1},s_{2},\cdots,s_{k},\cdots,s_{n})|L=s_{n},r=s_{k}</math>，好部定义为 <math>G=(s_{1},s_{2},\cdots,s_{k-1})</math>，即 <math>S=(G,B,L)</math>
- <math>S=(G,B,L).</math>
+通俗地说，好部是坏部之前的部分。好部可以为空。
-通俗地说，好部是坏部之前的部分．好部可以为空．
 == 展开 ==
 PrSS 的良序性已经得到证明，且其标准式的序等价于字典序，因此所有标准的 PrSS 表达式都一一对应着一个序数．
 对于一个合法的 PrSS 表达式 <math>S=(s_1,s_2,\ldots,s_{n-1},s_n)</math>，其展开规则如下：
-* 如果 <math>S</math> 是零表达式，则 <math>S</math> 代表序数 <math>0</math>.
+* 如果 <math>S</math> 是零表达式，则 <math>S</math> 代表序数 <math>0</math>
-* 如果 <math>S</math> 是后继表达式，则其前驱是 <math>S'=(s_1,s_2,\ldots,s_{n-1})</math>.
+* 如果 <math>S</math> 是后继表达式，则其前驱是 <math>S'=(s_1,s_2,\ldots,s_{n-1})</math>
-* 如果 <math>S</math> 是极限表达式，则根据前文定义确定好部、坏部，得到 <math>S=(G,B,L)</math>. 则其基本列的第 <math>m</math> 项定义为 <math>S[m]=(G,\underbrace{B,B,B,\cdots,B}_{m})</math>，其中 <math>m\in\mathbb{N}</math>. 或者说 <math>S</math> 的'''展开式'''为 <math>(G,\underbrace{B,B,B,\cdots}_{\omega})</math>.
+* 如果 <math>S</math> 是极限表达式，则根据前文定义确定好部、坏部，得到 <math>S=(G,B,L)</math>. 则其基本列的第 <math>m</math> 项定义为 <math>S[m]=(G,\underbrace{B,B,B,\cdots,B}_{m})</math>，其中 <math>m\in\mathbb{N}</math>. 或者说 <math>S</math> 的'''展开式'''为 <math>(G,\underbrace{B,B,B,\cdots}_{\omega})</math>
 举例：
@@ 第76行： / 第63行： @@
 <math>S=(0,1,{\color{red}2},3,3,{\color{green}3})</math>
-末项是标绿的 <math>{\color{green}3}</math>，坏根是从右往左数第一个比 <math>{\color{green}3}</math> 小的数，也就是标红色的 <math>{\color{red}2}</math>.
+末项是标绿的 <math>{\color{green}3}</math>，坏根是从右往左数第一个比 <math>{\color{green}3}</math> 小的数，也就是标红色的 <math>{\color{red}2}</math>。
-接下来，根据坏部的定义可以知道坏部是 <math>(2,3,3)</math>．
+接下来，根据坏部的定义可以知道坏部是 <math>(2,3,3)</math>。
-坏根之前的好部不用管，将末项抛弃
+坏根之前的好部不用管，将末项抛弃：
 <math>S=(0,1,{\color{red}2},3,3)</math>
-复制坏部
+复制坏部：
 <math>S=(0,1,{\color{red}2},3,3,{\color{red}2},3,3,{\color{red}2},3,3,\cdots)</math>
-我们就成功地展开了一个 PrSS 表达式．
+我们就成功地展开了一个 PrSS 表达式。
 == 与康托范式的对应 ==
-参见词条 [[PrSS VS 康托范式]]．
+参见词条 [[PrSS VS 康托范式]]。
 == 拓展 ==
 PrSS 记号有两种拓展：
-* 高维 PrSS，如 PrSS 原作者所创的 [[BMS]].
+* 高维 PrSS，如 PrSS 原作者所创的 [[BMS]]
 * 阶差 PrSS ，有两种形式：
-** [[长初等序列|LPrSS]] 及各种 [[Hydra]] 记号.
+** [[长初等序列|LPrSS]] 及各种 [[Hydra]] 记号
-** [[HPrSS]]，[[0-Y]]，[[Y序列]] 等复杂阶差型记号.
+** [[HPrSS]]，[[0-Y]]，[[Y序列]] 等复杂阶差型记号
-它们以 PrSS 序列为基础，刻画了非常巨大的序数．
+它们以 PrSS 序列为基础，刻画了非常巨大的序数。
 == 历史 ==
-在 2014/08/14，Bashicu 首次提出并使用 Basic 语言定义了 PrSS.<ref>Bashicu. basic言語で巨大数を作ってみたので上げてみる[EB/OL]. 2014, 08/14:109. https://gyafun.jp/ln/archive/ln10.html</ref>
+在 2014.8.14，Bashicu 首次提出并使用 Basic 语言定义了 PrSS。<ref>Bashicu. basic言語で巨大数を作ってみたので上げてみる[EB/OL]. 2014, 08/14:109. https://gyafun.jp/ln/archive/ln10.html</ref>
 == 脚注 ==
@@ 第110行： / 第97行： @@
 == 参考资料 ==
 <references />
 [[分类:入门]]
 [[分类:记号]]