超初等序列：修订间差异

←上一编辑

可视化wikitext

2025年8月20日 (三) 16:26的最新版本

超初等序列(Hyper Primitive Sequence System, HPrSS)，是一种Worm型序数记号，它是PrSS的一种扩展。

定义

合法表达式

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

结构

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

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

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

父项

对于 $m \in {1, 2, \dots, n}$ ，记 $p_{m} = \max {1 \leq p_{m} < m ∣ a_{p_{m}} < a_{m}}$ ，若这样的 $p_{m}$ 存在，则称 $a_{p_{m}}$ 为 $a_{m}$ 的父项。

如果这样的 $p_{m}$ 不存在，我们也可以把 $a_{m}$ 的父项定义为一个虚构的“第0项”，其值为 $a_{0} = 0$ 。

通俗的说， $a_{m}$ 的父项是在 $a_{m}$ 左边、最靠右的、且小于 $a_{m}$ 的项。

例如，在 $(1, 3, 5, 4, 1, 3)$ 中，4的父项是第一个3，而第二个1没有父项。

祖先

对于 $m \in {1, 2, \dots, n}$ ，记 $m_{0} = m$ ， $m_{i + 1} = p_{m_{i}}$ ， $P_{m} = {m_{i} ∣ i \geq 0}$ 我们将 $a_{m}$ 的祖先定义为所有 $a_{p} (p \in P_{m})$ 。

通俗地说，某一项的祖先是它本身、它的父项、父项的父项、父项的父项的父项……中的某一项。

例如， $(1, 4, 6, 7, 6, 7)$ 中，末项7的祖先是所有红色的项。

阶差

对于 $m \in {1, 2, \dots, n}$ ，若 $a_{m}$ 的父项是 $a_{p_{m}}$ ，则定义 $a_{m}$ 的阶差为 $d_{m} = a_{m} - a_{p_{m}}$ ;若没有父项，则定义 $a_{m}$ 的阶差为 $d_{m} = a_{m}$ 。

由父项的定义可知，阶差一定是正整数。

阶差序列

设 $a_{m}$ 的阶差为 $d_{m}$ ，我们把 $(d_{1}, d_{2}, \dots, d_{n})$ 称为 $(a_{1}, a_{2}, \dots, a_{n})$ 的阶差序列。

坏根

给定极限表达式 $(a_{1}, a_{2}, \dots, a_{n})$ ，其末项的阶差为 $d_{n}$ 。我们记序列的坏根为 $a_{r}$ ，其中 $r$ 定义如下：

若 $d_{n} = 1$ ，则 $r = p_{n}$ ，即序列的坏根定义末项的父项；

若 $d_{n} \geq 1$ ，则 $r = \max {k \in P_{n} | d_{k} < d_{n}}$ 。通俗地说，序列的坏根为末项的祖先中，最靠右的，且阶差小于末项阶差的项。

序列的阶差

序列的阶差定义为 $δ = a_{n} - a_{r} - 1$ ，这一点和 LPrSS 一致。

坏部&好部

坏部、好部的定义和 PrSS 一致：坏部 $B = (a_{r}, a_{r + 1}, \dots, a_{n - 1})$ ，好部 $G = (a_{1}, a_{2}, \dots, a_{r - 1})$ 。

展开

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

若 $S$ 为零表达式，则 $S$ 代表序数0；
若 $S$ 为后继表达式，则其前驱是 $S^{'} = (a_{1}, a_{2}, \dots, a_{n - 1})$ ；
若 $S$ 为极限表达式，根据前文定义确定坏根、阶差、好部、坏部；记 $B_{t} = (a_{r} + t δ, a_{r + 1} + t δ, \dots, a_{n - 1} + t δ)$ ，它可以看成坏部的每一项加上阶差的t倍，则其基本列的第 $m$ 项为 $S [m] = (G, B, B_{1}, B_{2}, \dots, B_{m})$ 。或者说， $S$ 的展开式为 $(G, B, B_{1}, B_{2}, \dots)$ 。

举例

考虑 HPrSS 表达式 $(1, 4, 6, 6)$ 。

首先，找出末项6的所有祖先项，用红色表示： $(1, 4, 6, 6)$ 。

其次，计算出阶差序列，为 $(1, 3, 2, 2)$ 。

然后，我们从末项的祖先项中，找到最右边的阶差小于2的项。这里4的阶差为3，我们跳过它，故坏根是首项1。

根据末项和坏根，我们得到了好部 $G = ()$ ，坏部 $B = (1, 4, 6)$ ，阶差 $δ = 6 - 1 - 1 = 4$ 。

根据坏部和阶差，我们可以求出 $B_{1} = (5, 8, 10)$ ， $B_{2} = (9, 12, 14)$ ，等等。

最后，我们得到了展开式 $(1, 4, 6, 6) = (1, 4, 6, 5, 8, 10, 9, 12, 14, \dots)$ 。

可以将其和 LPrSS 中相同表达式的展开进行对比。

与 PSS Hydra 的对应

HPrSS可以和PSS Hydra存在直接的转换关系，下面介绍互译算法。

说明：算法中出现的所有“序列”均指正整数序列，不需要为HPrSS的合法式。

HPrSS到PSS Hydra

给定一个HPrSS表达式 $S = (a_{1}, a_{2}, \dots, a_{n})$ ，设其对应的PSS Hydra表达式为 $P H (S)$ 。则：

如果 $S$ 为空序列，则 $P H (S) = 0$ 。
否则，记 $x_{1} = 1$ ， $x_{n + 1} = \min {k > x_{n} ∣ a_{k} \leq a_{x_{n}}}$ ，即 $a_{x_{n + 1}}$ 是 $a_{x_{n}}$ 右边第一个小于等于 $a_{x_{n}}$ 的项。这样 $S$ 就可以写成 $(a_{x_{1}}, S_{1}, a_{x_{2}}, S_{2}, \dots, a_{x_{k}}, S_{k})$ ，由 $a_{x_{n + 1}}$ 的定义可知 $S_{i}$ 中的每一项均大于 $a_{x_{n}}$ 。
我们有 $P H (S) = ψ_{a_{x_{1}}}^{H} (P H (S_{1} - a_{x_{1}})) + ψ_{a_{x_{2}}}^{H} (P H (S_{2} - a_{x_{2}})) + \dots + ψ_{a_{x_{k}}}^{H} (P H (S_{k} - a_{x_{k}}))$ ，其中 $S - a$ 为将 $S$ 的每一项都减去 $a$ 得到的序列。

例如，考虑LPrSS表达式 $(1, 4, 7, 6, 3, 5, 7)$

进行第二步，得到 $k = 1, x_{1} = 1$ ，故 $(1, 4, 7, 6, 3, 5, 7) = ψ_{1}^{H} ((3, 6, 5, 2, 4, 6))$

对 $(3, 6, 5, 2, 4, 6)$ 进行第二步，得到 $k = 2, x_{1} = 1, x_{2} = 4$ ，故 $(3, 6, 5, 2, 4, 6) = ψ_{3}^{H} ((3, 2)) + ψ_{2}^{H} ((2, 4))$

分别计算 $(3, 2)$ 和 $(2, 4)$ 对应的PSS Hydra，得到 $(3, 2) = ψ_{3}^{H} (0) + ψ_{2}^{H} (0)$ ， $(2, 4) = ψ_{2}^{H} (ψ_{2}^{H} (0))$

综上，我们得到了 $(1, 4, 7, 6, 3, 6, 8) = ψ_{1}^{H} (ψ_{3}^{H} (ψ_{3}^{H} (0) + ψ_{2}^{H} (0)) + ψ_{2}^{H} (ψ_{2}^{H} (ψ_{2}^{H} (0)))$

PSS Hydra到HPrSS

给定一个PSS Hydra表达式 $H$ ，设其对应的HPrSS表达式为 $L P (H)$ 。则：

如果 $H = 0$ ，则 $L P (H)$ 为空序列。
$L P (H_{1} + H_{2}) = (L P (H_{1}), L P (H_{2}))$ ，其中 $(S_{1}, S_{2})$ 为两个序列的拼接。
$L P (ψ_{x}^{H} (H)) = (x, (L P (H) + x))$ 。

@@ 第70行： / 第70行： @@
 首先，找出末项6的所有祖先项，用红色表示：<math>({\color{red}1},{\color{red}4},6,{\color{red}6})</math>。
-其次，计算出阶差序列，为<math>(1,2,2,2)</math>。
+其次，计算出阶差序列，为<math>(1,3,2,2)</math>。
 然后，我们从末项的祖先项中，找到最右边的阶差小于2的项。这里4的阶差为3，我们跳过它，故坏根是首项1。
@@ 第82行： / 第82行： @@
 可以将其和 [[长初等序列#举例|LPrSS 中相同表达式的展开]]进行对比。
-== 枚举 ==
+== 与 PSS Hydra 的对应 ==
+HPrSS可以和[[PSS Hydra]]存在直接的转换关系，下面介绍互译算法。
+说明：算法中出现的所有“序列”均指正整数序列，不需要为HPrSS的合法式。
+=== HPrSS到PSS Hydra ===
+给定一个HPrSS表达式<math>S=(a_1,a_2,\cdots,a_n)</math>，设其对应的PSS Hydra表达式为<math>PH(S)</math>。则：
+* 如果<math>S</math>为空序列，则<math>PH(S)=0</math>。
+* 否则，记<math>x_1=1</math>，<math>x_{n+1}=\min\{k>x_n\mid a_k\le a_{x_n}\}</math>，即<math>a_{x_{n+1}}</math>是<math>a_{x_n}</math>右边第一个小于等于<math>a_{x_n}</math>的项。这样<math>S</math>就可以写成<math>(a_{x_1},S_1,a_{x_2},S_2,\cdots,a_{x_k},S_k)</math>，由<math>a_{x_{n+1}}</math>的定义可知<math>S_i</math>中的每一项均大于<math>a_{x_n}</math>。
+* 我们有<math>PH(S)=\psi^H_{a_{x_1}}(PH(S_1-a_{x_1}))+\psi^H_{a_{x_2}}(PH(S_2-a_{x_2}))+\cdots+\psi^H_{a_{x_k}}(PH(S_k-a_{x_k}))</math>，其中<math>S-a</math>为将<math>S</math>的每一项都减去<math>a</math>得到的序列。
-== 与 PSS Hydra 的对应 ==
+例如，考虑LPrSS表达式<math>(1,4,7,6,3,5,7)</math>
+进行第二步，得到<math>k=1,x_1=1</math>，故<math>({\color{red}1},4,7,6,3,5,7)=\psi^H_1((3,6,5,2,4,6))</math>
+对<math>(3,6,5,2,4,6)</math>进行第二步，得到<math>k=2,x_1=1,x_2=4</math>，故<math>({\color{red}3},6,5,{\color{red}2},4,6)=\psi^H_3((3,2))+\psi^H_2((2,4))</math>
+分别计算<math>(3,2)</math>和<math>(2,4)</math>对应的PSS Hydra，得到<math>(3,2)=\psi^H_3(0)+\psi^H_2(0)</math>，<math>(2,4)=\psi^H_2(\psi^H_2(0))</math>
+综上，我们得到了<math>(1,4,7,6,3,6,8)=\psi^H_1(\psi^H_3(\psi^H_3(0)+\psi^H_2(0))+\psi^H_2(\psi^H_2(\psi^H_2(0)))</math>
+=== PSS Hydra到HPrSS ===
+给定一个PSS Hydra表达式<math>H</math>，设其对应的HPrSS表达式为<math>LP(H)</math>。则：
+* 如果<math>H=0</math>，则<math>LP(H)</math>为空序列。
+* <math>LP(H_1+H_2)=(LP(H_1),LP(H_2))</math>，其中<math>(S_1,S_2)</math>为两个序列的拼接。
+* <math>LP(\psi^H_x(H))=(x,(LP(H)+x))</math>。
+{{默认排序:序数记号}}
+[[分类:记号]]