初等序列系统

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}}$

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

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

例：

• $(0,1,1,2,2)$ 是一个合法的 PrSS 表达式
• $(\mathrm{\Omega },1,2)$ 不是一个合法的 PrSS 表达式，因为 $\mathrm{\Omega }\notin \mathbb{\mathbb{N}}$
• $(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 的极限表达式由以下四个部分组成：

1. 末项（Last Term）
2. 坏部（Bad Part）
3. 坏根（Bad Root）
4. 好部（Good Part）

末项：对于最大下标为 $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 良序性的证明

参见 PrSS的良序性。

与康托范式的对应

参见词条 PrSS VS 康托范式。

拓展

PrSS 记号有两种拓展：

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

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

历史

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