用户: Smile/初等序列

初等序列是一种用正整数序列来表示可数序数的方法.

初等序列能表示的序数较少, 它仅能表达不超过 ${\epsilon }_0$ 的序数. 但这表示方法有很多扩展, 可以表达相当大的可数序数.

1定义动机

试想我们按照如下的方法用正整数列来表达序数. 自然, $0$ 为空列. 序数增加 $1$, 则在数列后添加一项 $1$. 这样 $1=(1,)$, $2=(1,1)$, 这样直到 $\omega =(1,1,\cdots )$.

我们用 $1,2$ 表示 $1$ 的无限循环, 这样 $\omega =(1,2)$. 我们可以继续写 $\omega +1=(1,2,1)$, $\omega 2=(1,2,1,2)$, ${\omega }^2=(1,2,1,2,1,2,\cdots )$.

如何表达 $(1,2)$ 的无限循环呢? 我们自然可以用 $3$, 但这样就太浪费了. 初等序列的重要想法是, 我们先写出循环节, 然后用稍大的数表示无限循环. 这就解释了用 $(1,2)$ 而非 $(2)$ 来表示 $\omega$ 的原因. 这样就有 ${\omega }^2=(1,2,2)$.

我们可以继续写 ${\omega }^3=(1,2,2,2)$, ${\omega }^{\omega }=(1,2,3)$, 直到 ${\epsilon }_0=(1,2,3,4,\cdots )$.

2定义

设 $S=(a_0,\cdots ,a_m)$ 是正整数序列. 取最大的 $i<m$ (若存在) 使得 $a_i=a_m-1$. 对任何自然数 $n$, 定义 $Expand(S,n)$ 为序列 $(a_0,\cdots ,a_{i-1})+(a_i,\cdots ,a_{m-1})\times n$, 即先去除最后一项, 再把第 $i$ 项起的部分复制为 $n$ 份. $Expand(S,n)$ 叫做 $S$ 的初等序列展开.

我们下面来递归定义合法的初等序列, 及它们表示的可数序数.

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

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

注 2.2. 为了简化记号, 我们有时不写出 $Expand$, 而是用无穷序列来表示展开. 这表示法和第 1 节中的记号相容. 例如, 等式 $(1,2)=(1,1,1,1,\cdots )$ 有显然的含义. 特别地, 我们常不严格地称 $prss(1,2,3,\cdots )={\epsilon }_0$.

3基本性质

对于初等序列, 其结构相对简单, 我们对它的性质有完全具体的刻画. 这是它的各种扩展所不具有的.

命题 3.1. 设 $S=(a_0,\cdots ,a_m)$, $m\ge 0$. 以下条件等价.

1.	$S$ 是初等序列.
2.	$a_0=1$, 且对 $0<i\le m$, $a_i\le a_{i-1}+1$.

证明. (i) 推出 (ii) 是容易的. 为证明 (ii) 推出 (i), 只需再证明 (ii) 中的序列在展开关系下是良基的. 这由接下来的分析立即可得.

$\square$

我们先给出一些显然的观察.

引理 3.2. 设 $S,S^{\prime }$ 是超初等序列, 则 $S+S^{\prime }$ 是超初等序列, 且 $prss(S+S^{\prime })=prss(S)+prss(S^{\prime })$.

证明. 注意到当 $S^{\prime }$ 不以 $1$ 结尾时, $Expand(S+S^{\prime },n)$ = $S+Expand(S^{\prime },n)$. 由归纳即可证明, $S+\bullet$ 对初等序列封闭, 且有所要的序数关系.

$\square$

引理 3.3. 设 $S=(a_0,\cdots ,a_m)$ 为初等序列. 令 $p(S)=(1,a_0+1,\cdots ,a_m+1)$ 为将 $S$ 每个数增加 $1$, 并在前面添加 $1$ 得到的序列. 则 $p(S)$ 是初等序列, 且 $prss(p(S))={\omega }^{prss(S)}$.

证明. 注意到当 $S$ 不以 $1$ 结尾时, $Expand(p(S),n)$ = $p(Expand(S,n))$. 而 $S=S^{\prime }+(1,)$ 以 $1$ 结尾时, $Expand(p(S),n)=p(S^{\prime })\times n$. 由归纳即可证明, $p$ 对初等序列封闭, 且有所要的序数关系.

$\square$

从以上两个引理, 已经能证明命题 3.1, 并能给出所有初等序列的序数对应. 对每个初等序列, 把它按 $1$ 分为若干段, 再删去 $1$, 并把所有数减去 $1$, 得到一些新的初等序列. 计算这些初等序列的序数, 再作 $\omega$ 幂相加, 即得原来的初等序列的序数.

注 3.4. 容易发现, 一个无限序数对应的初等序列不唯一. 例如, $prss(1,1,2)=prss(1,2)=\omega$. 可以把表示同一个序数的初等序列中, 在字典序下最大的那个叫做典范形式. 由初等序列的上述具体计算, 典范形式显然存在, 且在上述计算中对应康托标准型.

对上述定义稍作修改, 我们就得到如下大数记号. 这定义实际上就是快速增长层级, 只需注意初等序列不但给出了序数表示法, 还同时给出了它们的基本列.

定义 3.5. 设 $S$ 是初等序列, $n$ 是自然数, 递归定义自然数 $S[n]$ 如下.

1.	若 $S=()$ 为空串, $S[n]=n+1$.
2.	若 $S=S^{\prime }+(1,)$ 末项为 $1$, $S[n]=S^{\prime }[S^{\prime }[\cdots S^{\prime }[n]]]$, 即 $S^{\prime }[\bullet ]$ 作用在 $n$ 上 $n$ 次.
3.	若 $S$ 以大于 $1$ 的正整数结尾, $S[n]=Expand(S,n)[n]$.

4例子

本节是一个表格, 列举了一些初等序列 (均为典范形式) 与序数的对应关系.

$()$	$0$
$(1)$	$1$
$(1,1)$	$2$
$(1,1,1)$	$3$
$(1,2)$	$\omega$
$(1,2,1)$	$\omega +1$
$(1,2,1,1)$	$\omega +2$
$(1,2,1,2)$	$\omega 2$
$(1,2,2)$	${\omega }^2$
$(1,2,2,2)$	${\omega }^3$
$(1,2,3)$	${\omega }^{\omega }$
$(1,2,3,1)$	${\omega }^{\omega }+1$
$(1,2,3,2)$	${\omega }^{\omega +1}$
$(1,2,3,3)$	${\omega }^{\omega 2}$
$(1,2,3,4)$	${\omega }^{{\omega }^{\omega }}$
$(1,2,3,4,5)$	${\omega }^{{\omega }^{{\omega }^{\omega }}}$
初等序列极限	${\epsilon }_0$