用户: Smile/超初等序列

超初等序列是初等序列的一个十分简单的扩展. 尽管如此, 它的表达能力十分强大. 事实上, 它可以表达所有小于 Buchholz 序数 $BO=\psi ({\Omega }_{\omega })$ 的序数. 这里 $\psi$ 是 Buchholz 的序数坍缩函数.

1定义动机

初等序列的极限是 ${\epsilon }_0=prss(1,2,3,4,\cdots )$. 自然的想法是, 虽然 $(1,2,3,4,\cdots )$ 不循环, 但它是等差数列, 用一个新的记号来表达它, 就可以越过 ${\epsilon }_0$. 在初等序列中, 相邻两项至多增长 $1$, 从而 $(1,3)$ 不是合法的初等序列.

在超初等序列中, 我们令 $(1,3)=(1,2,3,4,\cdots )$, $(1,3,5)=(1,3,4,6,7,9,\cdots )$, $(1,4)=(1,3,5,7,\cdots )$. 这样, 对任何自然数 $n$, $(1,n)$ 都是合法的超初等序列. 超初等序列表达序数的极限是序数升列 $hprss(1,n)$ 的极限, 常记为 $hprss(1,\omega )$.

2定义

相比于初等序列, 为定义超初等序列, 只需修改展开的定义. 我们下面定义超初等序列展开 $Expand$. 为此, 我们需要先构造两个自然数 $r,\delta$, 分别为循环节起始点和公差.

令 $S=(a_0,\cdots ,a_m)$. 令 $m_0=m$, 然后依次取 $m_i$ (直到不存在), 使得 $m_{i+1}$ 为小于 $m_i$ 且满足 $a_{m_{i+1}}<a_{m_i}$ 的数中最大者. 令 $N_i=a_{m_{i-1}}-a_{m_i}$ 为差序列.

若 $m_1$ 不存在, 则展开无定义. 下设 $m_1$ 存在.

若 $N_1=1$, 则令 $r=m_1$, $\delta =0$. 此时, 超初等序列展开即退化为初等序列展开.

下设 $N_1>1$. 我们寻找最小的 $j$ 使得 $N_j<N_1$.

若 $j$ 不存在, 则令 $r=1$, $\delta =a_m-1$.

若 $j$ 存在, 则令 $r=m_{j-1}$, $\delta =a_m-a_r-1$.

令展开 $Expand(S,n)=(a_0,\cdots ,a_{r-1})+{\sum }_{k=0}^{n-1}(a_r+k\delta ,\cdots ,a_{m-1}+k\delta )$. 此即为 $S$ 移除最后一项, 然后将循环节复制 $n$ 次, 每次增加公差.

注 2.1. 若假定序列首项为 $1$, 则公差的选取总是使得展开后序列的第 $m$ 项减少 $1$.

定义 2.2 (超初等序列). 超初等序列是如下递归定义的一些有限项正整数序列.

1.	空串 $S=\varnothing$ 是超初等序列. $hprss(\varnothing )=0$.
2.	若 $S=S^{\prime }+(1,)$ 以 $1$ 结尾, 且 $S^{\prime }$ 是超初等序列, 则 $S$ 是超初等序列. $hprss(S)=hprss(S^{\prime })+1$.
3.	若 $S$ 不以 $1$ 结尾, 且对所有自然数 $n$, $Expand(S,n)$ 存在且是超初等序列, 则 $S$ 是超初等序列. $hprss(S)$ 为序数升列 $hprss(Expand(S,n))$ 的极限.

3性质

与初等序列不同, 我们有如下断言.

命题 3.1. 所有首项为 $1$ 的正整数序列都是超初等序列.

本文不给出其证明.

由于这个命题, 我们更关心超初等序列的典范形式.

类似初等序列, 我们可以得到大数记号 $S[n]$, 定义与初等序列情形一致. 给定 $S$, 这关于 $n$ 的函数的快速增长层级增长率等于 $hprss(S)$.

TODO: 其他性质

4例子

例 4.1. 我们列举一些例子, 以便理解展开的过程. 其中, 关于 $r$, 注意根据本文习惯, 指标从 $0$ 开始. $$(1,3)=(1,2,3,4,5,\cdots ),r=0,\delta =1.$$$$(1,3,2)=(1,3,1,3,1,3,\cdots ),r=0,\delta =0.$$$$(1,3,3)=(1,3,2,4,3,5,\cdots ),r=0,\delta =1.$$$$(1,3,4)=(1,3,3,3,3,3,\cdots ),r=1,\delta =0.$$$$(1,3,4,6)=(1,3,4,5,6,7,\cdots ),r=2,\delta =1.$$$$(1,3,5)=(1,3,4,6,7,9,10,12,\cdots ),r=0,\delta =3.$$$$(1,3,5,5)=(1,3,5,4,6,8,7,9,11,\cdots ),r=0,\delta =4.$$$$(1,4,6,4)=(1,4,6,3,6,8,5,8,10,\cdots ),r=0,\delta =3.$$$$(1,4,6,5)=(1,4,6,4,6,4,6,\cdots ),r=1,\delta =0.$$$$(1,4,6,6)=(1,4,6,5,7,6,8,\cdots ),r=1,\delta =1.$$$$(1,4,6,7)=(1,4,6,6,6,6,6,\cdots ),r=2,\delta =0.$$$$(1,4,6,8)=(1,4,6,7,9,10,12,13,15,\cdots ),r=1,\delta =3.$$$$(1,4,6,9)=(1,4,6,8,11,13,15,18,20,\cdots ),r=0,\delta =8.$$

如初等序列, 本节剩余部分为一张表格, 给出了序数与典范形式的超初等序列的对应. 本节的序数坍缩函数, 第三栏为 Buchholz 的 $\phi$ 函数的序数指标形式, 第四栏为 Madore 的 $\phi$ 函数的序数指标形式.

$(1,3)$	${\epsilon }_0$	$\psi (\Omega )$	$\psi (0)$
$(1,3,2,4)$	${\epsilon }_0^2$	$\psi (\Omega +\psi (\Omega ))$
$(1,3,3)$	${\epsilon }_1$	$\psi (\Omega 2)$	$\psi (1)$
$(1,3,4)$	${ϵ}_{\omega }$	$\psi (\Omega \omega )$	$\psi (\omega )$
$(1,3,4,4)$	${ϵ}_{{\omega }^2}$	$\psi (\Omega {\omega }^2)$	$\psi ({\omega }^2)$
$(1,3,4,5)$	${ϵ}_{{\omega }^{\omega }}$	$\psi (\Omega ({\omega }^{\omega }))$	$\psi ({\omega }^{\omega })$
$(1,3,4,6)$	${ϵ}_{{ϵ}_0}$	$\psi (\Omega \psi (\Omega ))$	$\psi (\psi (0))$
$(1,3,5)$	$\phi (2,0)$	$\psi ({\psi }_1(\Omega ))$	$\psi (\Omega )$
$(1,3,5,7)$	$\phi (1,0,0)$	$\psi ({\psi }_1({\psi }_1(\Omega )))$	$\psi ({\Omega }^{\Omega })$
$(1,3,5,7,9)$	$LVO=\phi (1@(1,0))$	$\psi ({\psi }_1({\psi }_1({\psi }_1(\Omega ))))$	$\psi ({\Omega }^{{\Omega }^{\Omega }})$
$(1,4)$	$BHO$	$\psi ({\Omega }_2)$	$\psi ({\psi }_1(0))$
$(1,4,4)$		$\psi ({\Omega }_{2}2)$	$\psi ({\psi }_1(1))$
$(1,4,5)$		$\psi ({\Omega }_2\omega )$	$\psi ({\psi }_1(\omega ))$
$(1,4,6)$		$\psi ({\Omega }_2\Omega )$	$\psi ({\psi }_1(\Omega ))$
$(1,4,6,9)$		$\psi ({\Omega }_2{\psi }_1({\Omega }_2))$	$\psi ({\psi }_1({\psi }_1(\Omega )))$
$(1,4,7)$		$\psi ({\Omega }_2^2)$	$\psi ({\Omega }_2)$
$(1,5)$		$\psi ({\Omega }_3)$	$\psi ({\psi }_2(0))$
$(1,6)$		$\psi ({\Omega }_4)$	$\psi ({\psi }_3(0))$
$(1,n)$	($n\ge 2$)	$\psi ({\Omega }_n)$	$\psi ({\psi }_{n-1}(0))$
$(1,\omega )$		$\psi ({\Omega }_{\omega })$	$\psi ({\Omega }_{\omega })$

5参考文献

•	Yukito. Hyper primitive sequence system. https://googology.fandom.com/wiki/Hyper_primitive_sequence_system#cite_ref-4.