|
|
(未显示3个用户的18个中间版本) |
第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> | | <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)'''是一种 [[Beklemishev's Worm|Worm]] 型[[序数记号]]。 |
|
| |
|
| '''初等序列系统(Primative Sequence System,PrSS)'''是一种[[Worm]]型[[序数记号]]。
| |
| === 定义 === | | === 定义 === |
|
| |
|
| ==== 标准式 ==== | | ==== 合法式 ==== |
| 一个'''标准且合法'''的 <math>\rm PrSS</math> 是形如 | | 一个'''合法'''的 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_{0},s_{1},s_{2},\cdots,s_{n},s_{n+1},\cdots)|n \in \mathbb{N}</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>\langle \text{1} \rangle\ \quad s_{0}=0.</math><ref group="注">实际上,以1序列开头的PrSS也是被广为接受的,其更多被用于表示阶差型序列。但无论0或1为开头,均不影响PrSS的展开方式与增长率。</ref>
| |
| | |
| <math>\langle \text{2} \rangle\ \quad 0\leq s_{n+1}-s_{n}\leq 1.</math>
| |
|
| |
|
| '''例:''' | | '''例:''' |
|
| |
|
| <math>(0,1,1,2,2)</math> 是一个合法的<math>\rm PrSS</math>. | | * <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>(\Omega,1,2)</math> 是一个非法的<math>\rm PrSS</math>.
| |
|
| |
| <math>(0,2,4,6,8)</math> 是一个非法的<math>\rm PrSS</math>.
| |
| ==== 结构 ==== | | ==== 结构 ==== |
| | 合法的 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>
| |
| | |
| ===== 末项 =====
| |
| | |
| 对于最大下标为 <math>n</math> 的 <math>\rm PrSS</math> 序列 <math>S=(s_{0},s_{1},s_{2},\cdots,s_{n})</math>,其末项 <math>L=s_{n}</math>,即
| |
| | |
| <math>S=(s_{0},s_{1},s_{2},\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>S=(s_{0},s_{1},s_{2},\cdots,r,\cdots,L).</math>
| |
| | |
| ===== 坏部 =====
| |
|
| |
|
| 对于<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>,即
| | 一个 PrSS 的'''极限表达式'''由以下四个部分组成: |
|
| |
|
| <math>S=(s_{0},s_{1},s_{2},\cdots,r,B-r,L)</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>B-r</math> 表示 <math>B</math> 不包含 <math>r .</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_{k},\cdots,s_{n})|L=s_{n},r=s_{k}</math>,好部 <math>G=\{s_{j}|0\leq j <k\}</math>,即
| | 因为极限表达式满足 <math>L=s_n>0</math> 且 <math>s_1=0</math>,所以坏根总是存在的。 |
|
| |
|
| <math>S=(G,r,B-r,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> |
|
| |
|
| 对于<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>,即
| | 通俗地说,是坏根(含)到末项(不含)的部分。坏部最短为 1 项。 |
|
| |
|
| <math>S'=(G,0).</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>r</math> 有可能不存在。这将会导致不存在 坏部<math>B</math> 的 <math>\rm PrSS</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>序列所表示的序数为[[序数#后继序数|后继序数]],你很快就会在下文中见到它。
| |
|
| |
|
| === 展开 === | | === 展开 === |
| | PrSS 的良序性已经得到证明,且其标准式的序等价于字典序,因此所有标准的 PrSS 表达式都一一对应着一个序数. |
|
| |
|
| 由于<math>\rm PrSS</math>的字典序,所有标准的<math>\rm PrSS</math>都[[双射|一一对应]]着一个序数。
| | 对于一个合法的 PrSS 表达式 <math>S=(s_1,s_2,\ldots,s_{n-1},s_n)</math>,其展开规则如下: |
| 对于一个标准的<math>\rm PrSS</math>序列 <math>S=(G,B,L)</math>,定义 <math>m,S[m] \in \mathbb{N}</math>,其展开规则如下:
| |
| | |
| 如果展开次数 <math>m</math> 存在,
| |
| | |
| :若 <math>L=0</math>,则
| |
| ::<math>S[m]=(G,B,0)[m]=(G,\emptyset,0)[m]=(G)[m]+1.</math>
| |
| | |
| :若 <math>L\neq 0</math>,则
| |
| ::<math>S[m]=(G,B,L)[m]=(G,\underbrace{B,B,\cdots,B}_{m})[m].</math>
| |
| | |
| 如果展开次数 <math>m</math> 不存在,
| |
| :若 <math>L=0</math>,则
| |
| ::<math>S</math> 是[[序数#后继序数|后继序数]],且
| |
| ::<math>S=(G,B,0)=(G,\emptyset,0)=(G)+1.</math>
| |
| | |
| :若 <math>L\neq 0</math>,则
| |
| ::<math>S</math> 是[[序数#极限序数|极限序数]],且
| |
| ::<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>S</math> 经过有限次展开后,在第 <math>n</math> 次变为空序列,那么
| |
| | |
| <math>S=S[m]=n\in \mathbb{N}</math>
| |
| | |
| 即该 <math>\rm PrSS</math> 所对应的序数为[[序数#有限序数|有限序数]]([[自然数]])
| |
| | |
| === 形式化定义 ===
| |
| <math>\rm PrSS</math>序列可以看作是一个坍缩 / 折叠记号。
| |
| | |
| 末项就是序列的结尾,
| |
| | |
| 坏根就是从右往左数第一个比末项小的元素,
| |
| | |
| 坏部就是坏根到末项(不包括末项)之间的序列,可以理解为无限循环小数里的“循环节”
| |
| | |
| 好部就是除了坏部和末项外的所有东西。<ref group="注">好部被称之为“好部”可能是因为展开时好部完全不用动,看起来令人舒适,因而得名”好“。</ref>
| |
| | |
| | |
| | |
| 具体说来,末项非零的<math>\rm PrSS</math>序列的展开是让大的末项折叠了小坏根后的序列 <math>[\text{坏根},\text{末项})</math> 的重复。例:
| |
| | |
| <math>S=(0,1,2,{\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>2,3,3</math>是”循环节“,用上划线标出“循环节"
| |
| | |
| <math>S=(0,1,2,\overline{{\color{red}2},3,3},{\color{gree}3})</math>
| |
| | |
| 坏根之前的好部不用管,将末项抛弃
| |
|
| |
|
| <math>S=(0,1,2,\overline{{\color{red}2},3,3})</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=(0,1,2,\overline{{\color{red}2},3,3,{\color{red}2},3,3,{\color{red}2},3,3,\cdots})</math> | | <math>S=(0,1,{\color{red}2},3,3,{\color{green}3})</math> |
|
| |
|
| 我们就成功地展开了一个<math>\rm PrSS</math>序列。
| | 末项是标绿的 <math>{\color{green}3}</math>,坏根是从右往左数第一个比 <math>{\color{green}3}</math> 小的数,也就是标红色的 <math>{\color{red}2}</math>。 |
|
| |
|
| === 枚举 ===
| | 接下来,根据坏部的定义可以知道坏部是 <math>(2,3,3)</math>。 |
|
| |
|
| 在按照字典序对所有可能的<math>\rm PrSS</math>序列进行排序之后,我们可以用序数对这些序列逐个进行标号,每个序列都与一个序数一一对应。事实上,这种对应关系要远比相应的大数函数增长率的对应关系要更本质。
| | 坏根之前的好部不用管,将末项抛弃: |
|
| |
|
| 枚举过程中,会对特定的'''循环节'''标记颜色,以更清晰地体现“折叠”的过程。
| | <math>S=(0,1,{\color{red}2},3,3)</math> |
|
| |
|
| 可点击按钮“展开”以查看枚举。
| | 复制坏部: |
|
| |
|
| <div class="toccolours mw-collapsible mw-collapsed"> | | <math>S=(0,1,{\color{red}2},3,3,{\color{red}2},3,3,{\color{red}2},3,3,\cdots)</math> |
| <div class="mw-collapsible-content">
| |
| <math>()=0</math>
| |
|
| |
|
| <math>(0)=1</math>
| | 我们就成功地展开了一个 PrSS 表达式。 |
|
| |
|
| <math>(0,0)=2</math>
| | === PrSS 良序性的证明 === |
| | 参见 [[PrSS的良序性]]。 |
|
| |
|
| <math>(0,0,0)=3</math>
| | === 与康托范式的对应 === |
| | | 参见词条 [[PrSS VS 康托范式]]。 |
| <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,...)= \mathrm{Limit\ of\ PrSS} =\varepsilon_{0}</math>
| |
| | |
| </div>
| |
| </div>
| |
| | |
| | |
| 最终得到,<math>\rm PrSS</math>的[[增长率]]为<math>\varepsilon_{0}</math>
| |
|
| |
|
| === 拓展 === | | === 拓展 === |
| | PrSS 记号有两种拓展: |
| | * 高维 PrSS,如 PrSS 原作者所创的 [[BMS]] |
| | * 阶差 PrSS ,有两种形式: |
| | ** [[长初等序列|LPrSS]] 及各种 [[Kirby-Paris Hydra|Hydra]] 记号 |
| | ** [[HPrSS]],[[0-Y]],[[Y序列]] 等复杂阶差型记号 |
|
| |
|
| <math>\rm PrSS</math>序列有两种拓展:
| | 它们以 PrSS 序列为基础,刻画了非常巨大的序数。 |
| * 高维PrSS,如PrSS原作者所创的[[BMS]]
| |
| * 阶差PrSS,有两种形式:
| |
| ** [[LPrSS]]及各种[[Hydra]]记号
| |
| ** [[HPrSS]],[[0-Y]],[[Y序列]]等复杂阶差型记号
| |
| | |
| 它们以<math>\rm PrSS</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> |
|
| |
|
| 在2014/08/14,Bashicu首次提出并使用Basic语言定义了PrSS.<ref>Bashicu. basic言語で巨大数を作ってみたので上げてみる[EB/OL]. 2014, 08/14:109. https://gyafun.jp/ln/archive/ln10.html</ref>
| | == 参考资料 == |
| | | <references />{{默认排序:序数记号}} |
| === 脚注 ===
| |
| <references group="注" />
| |
| | |
| === 参考资料 ===
| |
| <references /> | |
| [[分类:入门]] | | [[分类:入门]] |
| [[分类:记号]] | | [[分类:记号]] |