初等序列系统

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

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

定义

合法式

一个合法的 PrSS 表达式是形如

$S=(s_1,s_2,\cdots ,s_n)|n,s_1,s_2,\cdots ,s_n\in \mathbb{\mathbb{N}}$ 

且满足以下条件的自然数列：

$⟨\text{1}⟩s_1=0.$

$⟨\text{2}⟩s_{k+1}-s_k\le 1\mathrm{\forall }k\in \{1,2\cdots ,n-1\}.$

例：

$(0,1,1,2,2)$ 是一个合法的 PrSS 表达式.

$(\mathrm{\Omega },1,2)$ 不是一个合法的 PrSS 表达式，因为 $\mathrm{\Omega }\notin \mathbb{\mathbb{N}}$.

$(0,2,4,6,8)$ 不是一个合法的 PrSS 表达式，因为不满足条件 $⟨\text{2}⟩$.

结构

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

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

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

1. 末项 $\mathrm{(}\mathrm{L}\mathrm{a}\mathrm{s}\mathrm{t}\mathrm{T}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{)}$.
2. 坏部 $\mathrm{(}\mathrm{B}\mathrm{a}\mathrm{d}\mathrm{P}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{)}$.
3. 坏根 $\mathrm{(}\mathrm{B}\mathrm{a}\mathrm{d}\mathrm{R}\mathrm{o}\mathrm{o}\mathrm{t}\mathrm{)}$.
4. 好部 $\mathrm{(}\mathrm{G}\mathrm{o}\mathrm{o}\mathrm{d}\mathrm{P}\mathrm{a}\mathrm{r}\mathrm{t}\mathrm{)}$.

末项

对于最大下标为 $n$ 的 PrSS 表达式 $S=(s_1,s_2,\cdots ,s_n)$，其末项 $L=s_n$，即

$S=(s_1,s_2,\cdots ,L).$

坏根

对于 $S=(s_1,s_2,\cdots ,s_n)|L=s_n$，令 $k=\max \{1\le k<n|s_k<s_n\}$，那么坏根定义为 $r=s_k$，即

$S=(s_1,s_2,\cdots ,r,\cdots ,L).$

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

因为极限表达式满足 $L=s_n>0$ 且 $s_1=0$，所以坏根总是存在的。

坏部

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

$S=(s_1,s_2,\cdots ,s_{k-1},B,L)$

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

好部

对于 $S=(s_1,s_2,\cdots ,s_k,\cdots ,s_n)|L=s_n,r=s_k$，好部定义为 $G=(s_1,s_2,\cdots ,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^{\prime }=(s_1,s_2,\dots ,s_{n-1})$.
• 如果 $S$ 是极限表达式，则根据前文定义确定好部、坏部，得到 $S=(G,B,L)$. 则其基本列的第 $m$ 项定义为 $S[m]=(G,\underset{m}{\underbrace{B,B,B,\cdots ,B}})$，其中 $m\in \mathbb{\mathbb{N}}$. 或者说 $S$ 的展开式为 $(G,\underset{\omega }{\underbrace{B,B,B,\cdots }})$.

举例：

$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,\cdots )$

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

枚举

在按照字典序对所有的 PrSS 标准式进行排序之后，我们可以用序数对这些序列逐个进行标号，每个序列都与一个序数一一对应。事实上，这种对应关系要远比相应的大数函数增长率的对应关系要更本质。

枚举过程中，会对特定的“循环节”标记颜色，以更清晰地体现“折叠”的过程。

可点击按钮“展开”以查看枚举。

$()=0$

$(0)=1$

$(0,0)=2$

$(0,0,0)=3$

$(0,1)=(0,0,\cdots ,0)=\omega$

$(0,1,0)=\omega +1$

$(0,1,0,0)=\omega +2$

$(0,1,0,1)=(0,1,0,0,\cdots ,0)=\omega \times 2$

$(0,1,0,1,0,1)=\omega \times 3$

$(0,1,1)=(0,1,0,1,\cdots ,0,1)={\omega }^2$

$(0,1,1,0)={\omega }^2+1$

$(0,1,1,0,1)={\omega }^2+\omega$

$(0,1,1,0,1,0)={\omega }^2+\omega +1$

$(0,1,1,0,1,0,1)={\omega }^2+\omega \times 2$

$(0,1,1,0,1,1)=(0,1,1,0,1,0,1,\cdots ,0,1)={\omega }^2\times 2$

$(0,1,1,0,1,1,0,1,1)={\omega }^2\times 3$

$(0,1,1,1)=(0,1,1,0,1,1,\cdots ,0,1,1)={\omega }^3$

$(0,1,1,1,1)={\omega }^4$

$(0,1,2)=(0,1,1,\cdots ,1)={\omega }^{\omega }$

$(0,1,2,0,1,2)={\omega }^{\omega }\times 2$

$(0,1,2,1)=(0,1,2,0,1,2,\cdots ,0,1,2)={\omega }^{\omega +1}$

$(0,1,2,1,0,1,2)={\omega }^{\omega +1}+{\omega }^{\omega }$

$(0,1,2,1,0,1,2,1)={\omega }^{\omega +1}\times 2$

$(0,1,2,1,1)=(0,1,2,1,0,1,2,1,\cdots ,0,1,2,1)={\omega }^{\omega +2}$

$(0,1,2,1,1,1)={\omega }^{\omega +3}$

$(0,1,2,1,2)=(0,1,2,1,1,\cdots ,1)={\omega }^{\omega \times 2}$

$(0,1,2,1,2,1)={\omega }^{\omega \times 2+1}$

$(0,1,2,1,2,1,2)={\omega }^{\omega \times 3}$

$(0,1,2,2)=(0,1,2,1,2,\cdots ,1,2)={\omega }^{{\omega }^2}$

$(0,1,2,2,1)={\omega }^{{\omega }^2+1}$

$(0,1,2,2,1,2)={\omega }^{{\omega }^2+\omega }$

$(0,1,2,2,1,2,1)={\omega }^{{\omega }^2+\omega +1}$

$(0,1,2,2,1,2,1,2)={\omega }^{{\omega }^2+\omega \times 2}$

$(0,1,2,2,1,2,2)=(0,1,2,2,1,2,1,2,\cdots ,1,2)={\omega }^{{\omega }^2*2}$

$(0,1,2,2,2)=(0,1,2,2,1,2,2,\cdots ,1,2,2)={\omega }^{{\omega }^3}$

$(0,1,2,3)=(0,1,2,2,\cdots ,2)={\omega }^{{\omega }^{\omega }}$

$(0,1,2,3,2)={\omega }^{{\omega }^{\omega +1}}$

$(0,1,2,3,2,3)={\omega }^{{\omega }^{\omega \times 2}}$

$(0,1,2,3,3)={\omega }^{{\omega }^{{\omega }^2}}$

$(0,1,2,3,4)=(0,1,2,3,3,\cdots ,3)={\omega }^{{\omega }^{{\omega }^{\omega }}}$

$(0,1,2,3,4,5,...)=\mathrm{L}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{t}\mathrm{o}\mathrm{f}\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}={\epsilon }_0$

最终得到，PrSS 的极限为 ${\epsilon }_0$.

与康托范式的对应

PrSS 和康托范式之间存在直接的转换关系．下面介绍 PrSS 到康托范式的转换：

对于待转换的 PrSS 表达式 $S$，首先找到 $S$ 中所有的项 $0$，以这些 $0$ 为起点把 $S$ 分为若干个以 $0$ 开头的子表达式，并在中间用加号连接．如果一个子表达式只有一项，即 $(0)$，则将其变为 $1$．否则，将 $(0,X)$ 变换为 ${\omega }^{X^{\prime }}$，其中 $X^{\prime }$ 是将 $X$ 中所有的项都减一后得到的表达式．

然后继续对 $X^{\prime }$ 递归地进行操作，直到无法操作为止，就得到了对应的康托范式．

例如 PrSS 表达式 $(0,1,2,2,0,1,2,1,1,0,1,2,1,1,0,1,1,1)$，首先把它分为若干个 $0$ 开头的子表达式并用加号连接，得到 $(0,1,2,2)+(0,1,2,1,1)+(0,1,2,1,1)+(0,1,1,1)$，随后将每个子表达式按照 $(0,X)\mapsto {\omega }^{X^{\prime }}$ 的形式变换，得到 ${\omega }^{(0,1,1)}+{\omega }^{(0,1,0,0)}+{\omega }^{(0,1,0,0)}+{\omega }^{(0,0,0)}$．随后，把指数上的 PrSS 继续递归变换．$(0,1,1)$ 变换为 ${\omega }^{(0,0)}={\omega }^{1+1}={\omega }^2$．$(0,1,0,0)$ 变换为 ${\omega }^1+1+1=\omega +2$．而 $(0,0,0)$ 就是 $1+1+1=3$．因此我们便得到了 $(0,1,2,2,0,1,2,1,1,0,1,2,1,1,0,1,1,1)$ 对应的康托范式 ${\omega }^{{\omega }^2}+{\omega }^{\omega +2}\times 2+{\omega }^3$．

${\displaystyle }$

拓展

PrSS 记号有两种拓展：

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

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

历史

在 2014/08/14，Bashicu 首次提出并使用 Basic 语言定义了 PrSS.