打开/关闭搜索
打开/关闭菜单
223
68
64
2725
Googology Wiki
打开/关闭外观设置菜单
打开/关闭个人菜单
未登录
未登录用户的IP地址会在进行任意编辑后公开展示。

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

来自Googology Wiki
更多操作
←上一编辑
可视化wikitext
Phyrion​（留言 | 贡献）
行政员、​界面管理员、​管理员
643次编辑
小无编辑摘要
Z​（留言 | 贡献）
监督员、​管理员
617次编辑
小无编辑摘要
 
（未显示5个用户的28个中间版本）
第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虽然结构简单，但是却是目前已知的最强大的递归核心的基础。<br /><span style='float:right'><del>——</del>曹知秋</span></div>
<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>曹知秋. 大数理论. ''(EB/OL)'', Vol.1, pp.53-54.  https://github.com/ZhiqiuCao/Googology</ref><br /><span style='float:right'><del>------</del> 曹知秋</span></div>


'''初等序列系统(Primative Sequence System,PrSS)'''是一种[[Worm]]型[[序数记号]]。
'''初等序列系统（Primative Sequence System, PrSS）'''是一种 [[Beklemishev's Worm|Worm]] 型[[序数记号]]。
==== 定义 ====


===== 标准式判定 =====
=== 定义 ===
一个'''标准且合法'''的 <math>\rm PrSS</math> 是形如 <math>S=(s_{0},s_{1},s_{2},\cdots,s_{n},s_{n+1},\cdots)|n \in \mathbb{N}</math> 且满足以下所有条件的序列：


<math>\langle \text{1} \rangle\ \quad s_{0}=0.</math>
==== 合法式 ====
一个'''合法'''的 PrSS 表达式是形如 <math>S=(s_{1},s_{2},\cdots,s_{n})|n,s_{1},s_{2},\cdots,s_{n}\in\mathbb{N}</math>


<math>\langle \text{2} \rangle\ \quad 0\leq s_{n+1}-s_{n}\leq 1.</math>
且满足 <math>s_1=0,s_{k+1}-s_k\leqslant1(k=1,2,\cdots n-1)</math> 的自然数列（特别地，空序列 <math>()</math> 是合法的 PrSS 表达式）


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


<math>(0,1,1,2,2)</math>是一个合法的PrSS序列.
'''例：'''


<math>(\Omega,1,2)</math>是一个非法的PrSS序列.
* <math>(0,1,1,2,2)</math> 是一个合法的 PrSS 表达式
* <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序列.
==== 结构 ====
===== 结构 =====
合法的 PrSS 表达式可以分为零表达式、后继表达式、极限表达式，其定义如下：


一个'''标准的'''<math>\rm PrSS</math>由以下四个部分组成：
*'''零表达式'''：满足 <math>n=0</math> 的表达式，即空序列 <math>()</math>
# 末项 <math>\mathrm{(Last\ Term)}</math>
*'''后继表达式'''：满足 <math>n>0</math> 且 <math>s_{n}=0</math> 的表达式，例如 <math>(0,1,2,0)</math>
# 坏部 <math>\mathrm{(Bad\ Part)}</math>
*'''极限表达式'''：满足 <math>n>0</math> 且 <math>s_{n}>0</math> 的表达式，例如 <math>(0,1,2,1)</math>
# 坏根 <math>\mathrm{(Bad\ Root)}</math>
# 好部 <math>\mathrm{(Good\ Part)}</math>


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


对于最大下标为 <math>n</math> 的 <math>\rm PrSS</math> 序列 <math>S=(s_{0},s_{1},s_{2},\cdots,s_{n})</math>，其末项 <math>L=s_{n}</math>，即
# 末项（Last Term）
# 坏部（Bad Part）
# 坏根（Bad Root）
# 好部（Good Part）
'''末项：'''对于最大下标为 <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_{0},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,r,\cdots,L)</math>


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


对于<math>S=(s_{0},s_{1},s_{2},\cdots,s_{n})|L=s_{n}</math>，若<math>k=max(0 \leq k < n|s_{k}<s_{n})</math>，那么坏根 <math>r=s_{k}</math>，即
因为极限表达式满足 <math>L=s_n>0</math> 且 <math>s_1=0</math>，所以坏根总是存在的。


<math>S=(s_{0},s_{1},s_{2},\cdots,r,\cdots,L).</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>


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


对于<math>S=(s_{0},s_{1},s_{2},\cdots,s_{k},\cdots,s_{n})|L=s_{n},r=s_{k}</math>，坏部 <math>B=\{s_{i}|k\leq i <n\}</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=(s_{0},s_{1},s_{2},\cdots,r,B-r,L)</math>
通俗地说，好部是坏部之前的部分。好部可以为空。


其中 <math>B-r</math> 表示 <math>B</math> 不包含 <math>r .</math>
=== 展开 ===
PrSS 的良序性已经得到证明，且其标准式的序等价于字典序，因此所有标准的 PrSS 表达式都一一对应着一个序数．


'''好部'''
对于一个合法的 PrSS 表达式 <math>S=(s_1,s_2,\ldots,s_{n-1},s_n)</math>，其展开规则如下：


对于<math>S=(s_{0},s_{1},s_{2},\cdots,s_{k},\cdots,s_{n})|L=s_{n},r=s_{k}</math>，好部 <math>G=\{s_{j}|0\leq j <k\}</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=(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=(G,r,B-r,L).</math>
举例：


对于<math>S=(s_{0},s_{1},s_{2},\cdots,s_{n})|L=s_{n}=0</math>，好部 <math>G=\{s_{j}|0\leq j <n\}</math>，即
<math>S=(0,1,{\color{red}2},3,3,{\color{green}3})</math>


<math>S=(G,0).</math>
末项是标绿的 <math>{\color{green}3}</math>，坏根是从右往左数第一个比 <math>{\color{green}3}</math> 小的数，也就是标红色的 <math>{\color{red}2}</math>。


可以注意到，根据坏根的定义 <math>r</math> 有可能不存在。这将会导致不存在 坏部<math>B</math> 的<math>PrSS</math>序列产生。例如：
接下来，根据坏部的定义可以知道坏部是 <math>(2,3,3)</math>。


* <math>(0,1,2,1,0)</math>
坏根之前的好部不用管，将末项抛弃：
* <math>(0,1,0,0,0)</math>
* <math>(0,0,0,0,0)</math>


实际上，这种<math>\rm PrSS</math>序列所表示的序数为[[序数|后继序数]]，你很快就会在下文中见到它。
<math>S=(0,1,{\color{red}2},3,3)</math>


==== 展开 ====
复制坏部：


所有标准的<math>\rm PrSS</math>序列都对应着一个序数。
<math>S=(0,1,{\color{red}2},3,3,{\color{red}2},3,3,{\color{red}2},3,3,\cdots)</math>
对于一个标准的<math>\rm PrSS</math>序列 <math>S=(G,B,L)</math>，定义 <math>m,S[m] \in \mathbb{N}</math>，其展开规则如下：


若 <math>m</math> 存在，
我们就成功地展开了一个 PrSS 表达式。


:若 <math>L=0</math>，
=== PrSS 良序性的证明 ===
参见 [[PrSS的良序性]]。


::<math>S[m]=(G,B,0)[m]=(G,B)[m]+1.</math>
=== 与康托范式的对应 ===
参见词条 [[PrSS VS 康托范式]]。


:若 <math>L\neq 1</math>，
=== 拓展 ===
::<math>S[m]=(G,B,L)[m]=(G,\underbrace{B,B,\cdots,B}_{m})[m].</math>
PrSS 记号有两种拓展：
* 高维 PrSS，如 PrSS 原作者所创的 [[BMS]]
* 阶差 PrSS ，有两种形式：
** [[长初等序列|LPrSS]] 及各种 [[Kirby-Paris Hydra|Hydra]] 记号
** [[HPrSS]]，[[0-Y]]，[[Y序列]] 等复杂阶差型记号


若 <math>m</math> 不存在，
它们以 PrSS 序列为基础，刻画了非常巨大的序数。
:若 <math>L=0</math>，


::<math>S=(G,B,0)=(G,B)+1.</math>
=== 历史 ===
在 2014.8.14，Bashicu 首次提出并使用 Basic 语言定义了 PrSS。<ref>Bashicu, H. (2014). basic言語で巨大数を作ってみたので上げてみる [I tried creating a huge number in basic language, so I thought I'd share it.]. ''(EB/OL)''. https://gyafun.jp/ln/archive/ln10.html</ref>


:若 <math>L\neq 1</math>，
== 参考资料 ==
::<math>S</math> 是[[序数|极限序数]]，且
<references />{{默认排序:序数记号}}
::<math>S=sup\{(G),(G,B),(G,B,B),(G,B,B,B),\cdots\}.</math>
[[分类:入门]]
 
[[分类:记号]]
若 <math>L=\emptyset</math>，
:<math>S[m]=S=0.</math>
 
显然，如果末项为<math>0</math>，将不存在坏根；此时的<math>B</math>应被理解为删除<math>S</math>有限次末项的<math>0</math>后所得极限序数的坏部；如果经过有限次删除后，<math>S</math>最终变为空序列，那么 <math>S=S[m] \in \mathbb{N}</math>
 
==== 形式化定义 ====
<math>\rm PrSS</math>序列可以看作是一个坍缩 / 折叠记号。
 
末项就是序列的结尾，
 
坏根就是从右往左数第一个比末项小的元素，
 
坏部就是坏根到末项（不包括末项）之间的序列，
 
好部就是除了坏部和末项外的所有东西。<ref group="footnotes">好部被称之为“好部”可能是因为展开时好部完全不用动，看起来令人舒适，因而得名”好“。</ref>
 
 
 
具体说来，末项非零的<math>\rm PrSS</math>是让序列末项折叠序列 <math>[\text{坏根},\text{末项})</math> 的重复。例：
 
<math>S=(0,1,2,{\color{red}2},3,3,3)</math>
 
末项：<math>L=3</math>
 
坏根是从右往左数第一个比3小的数，也就是标红色的2.
 
接下来标出坏部（下划线）：
 
<math>S=(0,1,2,\underline{{\color{red}2},3,3},3)</math>
 
 
接下来，好部不用管，然后将末项抛弃：
 
<math>S=(0,1,2,\underline{{\color{red}2},3,3})</math>
 
然后复制坏部：
 
<math>S=(0,1,2,\underline{{\color{red}2},3,3},\underline{{\color{red}2},3,3},\underline{{\color{red}2},3,3},\cdots)</math>
 
我们就成功地展开了一个<math>\rm PrSS</math>序列。
 
==== 枚举 ====
 
<math>()=0</math>
 
<math>(0)=1</math>
 
<math>(0,0)=2</math>
 
<math>(0,0,0)=3</math>
 
<math>(0,1)=({\color{red}0},{\color{green}0},\cdots,{\color{blue}0})=\omega</math>
 
<math>(0,1,0)=\omega+1</math>
 
<math>(0,1,0,0)=\omega+2</math>
 
<math>(0,1,0,1)=(0,1,{\color{red}0},{\color{green}0},\cdots,{\color{blue}0})=\omega\times 2</math>
 
<math>(0,1,0,1,0,1)=\omega\times 3</math>
 
<math>(0,1,1)=({\color{red}0,1},{\color{green}0,1},\cdots,{\color{blue}0,1})=\omega^{2}</math>
 
<math>(0,1,1,0)=\omega^{2}+1</math>
 
<math>(0,1,1,0,1)=\omega^{2}+\omega</math>
 
<math>(0,1,1,0,1,0)=\omega^{2}+\omega+1</math>
 
<math>(0,1,1,0,1,0,1)=\omega^{2}+\omega\times 2</math>
 
<math>(0,1,1,0,1,1)=(0,1,1,{\color{red}0,1},{\color{green}0,1},\cdots,{\color{blue}0,1})=\omega^{2}\times 2</math>
 
<math>(0,1,1,0,1,1,0,1,1)=\omega^{2}\times 3</math>
 
<math>(0,1,1,1)=({\color{red}0,1,1},{\color{green}0,1,1},\cdots,{\color{blue}0,1,1})=\omega^{3}</math>
 
<math>(0,1,1,1,1)=\omega^{4}</math>
 
<math>(0,1,2)=(0,{\color{red}1},{\color{green}1},\cdots,{\color{blue}1})=\omega^{\omega}</math>
 
<math>(0,1,2,0,1,2)=\omega^{\omega}\times 2</math>
 
<math>(0,1,2,1)=({\color{red}0,1,2},{\color{green}0,1,2},\cdots,{\color{blue}0,1,2})=\omega^{\omega+1}</math>
 
<math>(0,1,2,1,0,1,2)=\omega^{\omega+1}+\omega^{\omega}</math>
 
<math>(0,1,2,1,0,1,2,1)=\omega^{\omega+1}\times 2</math>
 
<math>(0,1,2,1,1)=({\color{red}0,1,2,1},{\color{green}0,1,2,1},\cdots,{\color{blue}0,1,2,1})=\omega^{\omega+2}</math>
 
<math>(0,1,2,1,1,1)=\omega^{\omega+3}</math>
 
<math>(0,1,2,1,2)=(0,1,2,{\color{red}1},{\color{green}1},\cdots,{\color{blue}1})=\omega^{\omega\times 2}</math>
 
<math>(0,1,2,1,2,1)=\omega^{\omega\times 2+1}</math>
 
<math>(0,1,2,1,2,1,2)=\omega^{\omega\times 3}</math>
 
<math>(0,1,2,2)=(0,{\color{red}1,2},{\color{green}1,2},\cdots,{\color{blue}1,2})=\omega^{\omega^{2}}</math>
 
<math>(0,1,2,2,1)=\omega^{\omega^{2}+1}</math>
 
<math>(0,1,2,2,1,2)=\omega^{\omega^{2}+\omega}</math>
 
<math>(0,1,2,2,1,2,1)=\omega^{\omega^{2}+\omega+1}</math>
 
<math>(0,1,2,2,1,2,1,2)=\omega^{\omega^{2}+\omega\times 2}</math>
 
<math>(0,1,2,2,1,2,2)=(0,1,2,2,{\color{red}1,2},{\color{green}1,2},\cdots,{\color{blue}1,2})=\omega^{\omega^{2}*2}</math>
 
<math>(0,1,2,2,2)=(0,{\color{red}1,2,2},{\color{green}1,2,2},\cdots,{\color{blue}1,2,2})=\omega^{\omega^{3}}</math>
 
<math>(0,1,2,3)=(0,1,{\color{red}2},{\color{green}2},\cdots,{\color{blue}2})=\omega^{\omega^{\omega}}</math>
 
<math>(0,1,2,3,2)=\omega^{\omega^{\omega+1}}</math>
 
<math>(0,1,2,3,2,3)=\omega^{\omega^{\omega\times 2}}</math>
 
<math>(0,1,2,3,3)=\omega^{\omega^{\omega^{2}}}</math>
 
<math>(0,1,2,3,4)=(0,1,2,{\color{red}3},{\color{green}3},\cdots,{\color{blue}3})=\omega^{\omega^{\omega^{\omega}}}</math>
 
<math>(0,1,2,3,4,5,...)=Limit\ of\ PrSS=\varepsilon_{0}</math>
 
==== 拓展 ====
 
<math>\rm PrSS</math>序列有两种拓展：
* 高维PrSS，如PrSS原作者所创的[[BMS]]
* 阶差PrSS，有两种形式：
** [[LPrSS]]及各种[[Hydra]]记号
** [[HPrSS]]，[[0-Y]]，[[Y序列]]等复杂阶差型记号
 
它们以<math>\rm PrSS</math>序列为基础，刻画了非常巨大的序数。
 
==== 历史 ====
 
在2014/08/14，Bashicu首次提出并使用Basic语言定义了PrSS.<ref>Bashicu. basic言語で巨大数を作ってみたので上げてみる[EB/OL]. 2014, 08/14:109. https://gyafun.jp/ln/archive/ln10.html</ref>
 
==== 脚注 ====
<references group="footnotes" />
 
==== 参考资料 ====

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

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

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

定义

合法式

一个合法的 PrSS 表达式是形如 S=(s1,s2,⋯,sn)|n,s1,s2,⋯,sn∈ℕ

且满足 s1=0,sk+1−sk⩽1(k=1,2,⋯n−1) 的自然数列（特别地，空序列 () 是合法的 PrSS 表达式）

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

例：

  • (0,1,1,2,2) 是一个合法的 PrSS 表达式
  • (Ω,1,2) 不是一个合法的 PrSS 表达式，因为 Ω∉ℕ
  • (0,2,4,6,8) 不是一个合法的 PrSS 表达式，因为不满足条件 sk+1−sk⩽1

结构

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

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

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

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

末项：对于最大下标为 n 的 PrSS 表达式 S=(s1,s2,⋯,sn)，其末项 L=sn，即 S=(s1,s2,⋯,L)

坏根：对于 S=(s1,s2,⋯,sn)|L=sn，令 k=max⁡{1≤k<n|sk<sn}，那么坏根定义为 r=sk，即 S=(s1,s2,⋯,r,⋯,L)

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

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

坏部：对于 S=(s1,s2,⋯,sk,⋯,sn)|L=sn,r=sk，坏部定义为 B=(sk,sk+1,⋯,sn−1)，即 S=(s1,s2,⋯,sk−1,B,L)

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

好部：对于 S=(s1,s2,⋯,sk,⋯,sn)|L=sn,r=sk，好部定义为 G=(s1,s2,⋯,sk−1)，即 S=(G,B,L)

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

展开

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

对于一个合法的 PrSS 表达式 S=(s1,s2,…,sn−1,sn)，其展开规则如下：

  • 如果 S 是零表达式，则 S 代表序数 0
  • 如果 S 是后继表达式，则其前驱是 S′=(s1,s2,…,sn−1)
  • 如果 S 是极限表达式，则根据前文定义确定好部、坏部，得到 S=(G,B,L). 则其基本列的第 m 项定义为 S[m]=(G,B,B,B,⋯,B⏟m)，其中 m∈ℕ. 或者说 S 的展开式为 (G,B,B,B,⋯⏟ω)

举例：

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,⋯)

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

PrSS 良序性的证明

参见 PrSS的良序性。

与康托范式的对应

参见词条 PrSS VS 康托范式。

拓展

PrSS 记号有两种拓展：

  • 高维 PrSS，如 PrSS 原作者所创的 BMS
  • 阶差 PrSS ，有两种形式：

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

历史

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

参考资料

  1. ↑ 曹知秋. 大数理论. (EB/OL), Vol.1, pp.53-54. https://github.com/ZhiqiuCao/Googology
  2. ↑ Bashicu, H. (2014). basic言語で巨大数を作ってみたので上げてみる [I tried creating a huge number in basic language, so I thought I'd share it.]. (EB/OL). https://gyafun.jp/ln/archive/ln10.html
检索自“http://wiki.googology.top/index.php?title=初等序列系统&oldid=2135”