PrSS的良序性

PrSS 没有无穷降链

首先我们将 PrSS 的每个合法表达式 $S$ 对应于一个不超过 ${\epsilon }_0$ 的序数 $F(S)$。然后我们证明 PrSS 表达式展开时，其对应的序数严格递减。于是就可以依据 ${\epsilon }_0$ 的良序性说明 PrSS 没有无穷降链。

第一步：将 PrSS 的每个合法表达式对应于一个不超过 ${\epsilon }_0$ 的序数。

对 PrSS 表达式的长度归纳定义。

任取 PrSS 合法表达式 $S=(a_1,a_2,\cdots ,a_n)$。

若 $n=0$，则 $F(S)=0<{\epsilon }_0$。

若 $n>0$，分两种情况讨论：

• 若 $\mathrm{\forall }i\in \{2,3,\cdots ,n\},a_i\ne 0$，则取 $T=(a_2-1,a_3-1,\cdots ,a_n-1)$。
  不难验证，$T$ 是合法的 PrSS 表达式，且 $T$ 的长度比 $S$ 的长度短。令 $F(S)={\omega }^{F(T)}$。
  因为 $F(T)<{\epsilon }_0$，所以 $F(S)<{\epsilon }_0$。
• 否则，设 $S$ 中有 $r$ 项为零，且 $a_{k_1}=a_{k_2}=\cdots =a_{k_r}=0$，其中 $1=k_1<k_2<k_3<\cdots <k_r<k_{r+1}=n+1$。
  取 $S_i=(a_{k_i},a_{k_i+1},\cdots ,a_{k_{i+1}-1}),i=1,2,\cdots ,r$，不难验证 $S_1,S_2,\cdots ,S_r$ 都是合法的 PrSS 表达式，且它们的长度都比 $S$ 短。
  令 $F(S)=F(S_1)+F(S_2)+\cdots +F(S_r)$。
  因为 $F(S_1),F(S_2),\cdots ,F(S_r)<{\epsilon }_0$，所以 $F(S)<{\epsilon }_0$。

第二步：证明 PrSS 表达式展开时，其对应的序数严格递减。

对 PrSS 表达式的长度归纳证明。

任取 PrSS 表达式 $S=(a_1,a_2,\cdots ,a_n)$。

若 $n=0$，则 $S$ 无法展开。下面讨论 $n>0$ 的情况。

若 $a_n=0$，则 $S$ 的展开式（前驱表达式）是 $T=(a_1,a_2,\cdots ,a_{n-1})$。分为两种情况讨论：

• 若 $\mathrm{\forall }i\in \{2,3,\cdots ,n\},a_i\ne 0$，则 $S=(0)$，$F(S)=1$，$T=()$，$F(T)=0$，$F(T)<F(S)$。
• 否则，设 $S$ 中有 $r$ 项为零，且 $a_{k_1}=a_{k_2}=\cdots =a_{k_r}=0$，其中 $1=k_1<k_2<k_3<\cdots <k_r=n<k_{r+1}=n+1$。
  取 $S_i=(a_{k_i},a_{k_i+1},\cdots ,a_{k_{i+1}-1}),i=1,2,\cdots ,r$，则 $F(S)=F(S_1)+F(S_2)+\cdots +F(S_r)$。
  注意到 $S_r=(0)$，$F(S_r)=1$，所以 $F(T)=F(S_1)+F(S_2)+\cdots +F(S_{r-1})$，所以 $F(S)=F(T)+1>F(T)$。

若 $a_n\ne 0$，分为三种情况讨论：

• 若 $S$ 中有不止一项是零。
  设 $S$ 中有 $r>1$ 项为零，且 $a_{k_1}=a_{k_2}=\cdots =a_{k_r}=0$，其中 $1=k_1<k_2<k_3<\cdots <k_r<k_{r+1}=n+1$。
  取 $S_i=(a_{k_i},a_{k_i+1},\cdots ,a_{k_{i+1}-1}),i=1,2,\cdots ,r$，则 $F(S)=F(S_1)+F(S_2)+\cdots +F(S_r)$。
  设 $S$ 的坏根为 $a_x$。不难看出，$x\ge k_r$。
  设 $S_r$ 的基本列的第 $p$ 项是 $V_p$。由 PrSS 展开规则，$S$ 的基本列的第 $p$ 项是 $U_p=(S_1,S_2,\cdots ,S_{r-1},V_p)$。
  因为 $S_r$ 的长度比 $S$ 短，根据归纳假设，有 $F(V_p)<F(S_r)$。
  设 $V_p=(b_1,b_2,\cdots ,b_m)$ 中有 $s$ 项为零，且 $b_{l_1}=b_{l_2}=\cdots =b_{l_s}=0$，其中 $1=l_1<l_2<l_3<\cdots <l_s<l_{s+1}=m+1$。
  取 $T_i=(b_{l_i},b_{l_i+1},\cdots ,b_{l_{i+1}-1}),i=1,2,\cdots ,s$，则 $F(V_p)=F(T_1)+F(T_2)+\cdots +F(T_s)$。
  所以 $$\begin{array}{rl}F(U_s)& =F(S_1)+F(S_2)+\cdots +F(S_{r-1})+F(T_1)+F(T_2)+\cdots +F(T_s)\\ & =F(S_1)+F(S_2)+\cdots +F(S_{r-1})+(F(T_1)+F(T_2)+\cdots +F(T_s))\\ & =F(S_1)+F(S_2)+\cdots +F(S_{r-1})+F(V_s)\\ & <F(S_1)+F(S_2)+\cdots +F(S_{r-1})+F(S_r)\\ & =F(S)\end{array}$$
• 若 $S$ 中仅有首项为零，且末项为 $a_n=1$。
  令 $T_1=(a_1,a_2,\cdots ,a_{n-1})$。由 PrSS 展开规则，不难看出 $S$ 的基本列的第 $p$ 项是 $U_p=(T_1,T_1,\cdots ,T_1)$，其中有 $p$ 个 $T_1$。
  显然 $n\ge 2$，所以 $F(T_1)>0$。
  那么 $F(U_p)=F(T_1)+F(T_1)+\cdots +F(T_1)=F(T_1)\times p<F(T_1)\times \omega$。
  令 $T_2=(a_2-1,a_3-1,\cdots ,a_n-1)$，则 $F(S)={\omega }^{F(T_2)}$。
  令 $T_3=(a_2-1,a_3-1,\cdots ,a_{n-1}-1)$，则 $F(T_1)={\omega }^{F(T_3)}$。
  因为 $a_n-1=0$，所以 $F(T_2)=F(T_3)+1$，所以 $F(S)={\omega }^{F(T_2)}={\omega }^{F(T_3)+1}={\omega }^{F(T_3)}\times \omega =F(T_1)\times \omega >F(U_p)$。
• 若 $S$ 中仅有首项为零，且末项为 $a_n\ne 1$。
  令 $T=(a_2-1,a_3-1,\cdots ,a_n-1)$，因为 $a_n-1\ne 0$，所以 $T$ 是极限表达式。
  设 $T$ 的基本列的第 $k$ 项是 $T_k=(b_1,b_2,\cdots ,b_{m_k})$，则由 PrSS 展开规则可以看出 $S$ 的基本列的第 $k$ 项是 $S_k=(0,b_1+1,b_2+1,\cdots ,b_{m_k}+1)$。
  根据归纳假设有 $F(T_k)<F(T)$，所以 $F(S_k)={\omega }^{F(T_k)}<{\omega }^{F(T)}=F(S)$。

证毕。

以上，我们证明了 PrSS 表达式的展开过程不会无限进行，即不存在无穷降链。

至此，PrSS 已经是一个合格的序数记号了。但我们不止于此，我们要给出判断 PrSS 表达式是否标准的方法，并证明 PrSS 标准式的序是字典序。

PrSS 标准表达式

PrSS 的极限基本列是 $(),(0),(0,1),(0,1,2),\cdots$。PrSS 的极限基本列的第 $n$ 项是 $L_n=(0,1,2,\cdots ,n-1)$。

定义（PrSS 标准表达式）

一个 PrSS 表达式 $S$ 是 PrSS 标准表达式（简称 PrSS 标准式），当且仅当存在 $n$ 使得极限基本列的第 $n$ 项 $L_n$ 可以经过若干次展开得到 $S$。

简单地说，标准式就是能从极限基本列展开得到的表达式。对于大部分的序数记号，存在合法但不标准的表达式。这些不标准的合法表达式往往也能对应于一个序数（例如上一节的映射 $F$ 不要求表达式是标准的），但这将导致不同的合法表达式对应于同一个序数。对应于同一个序数的不同合法表达式，例如 $(0,1)$ 和 $(0,0,1)$ 都是对应于 $\omega$ 的表达式，彼此之间无法展开成对方。这意味着合法表达式集不是全序，更不是良序。不同的标准表达式则不会对应于同一个序数，标准表达式集确实是良序的。

在这一节，我们将给出 PrSS 标准式的必要条件。该条件实际上也是充分的，不过充分性将在下一节证明。在此之前，我们先来定义字典序的概念。

定义（字典序）

设 $A$ 是一个全序集，其上的全序是 $\le$。考虑两个数列 $S=(a_1,a_2,\cdots ,a_n)$ 和 $T=(b_1,b_2,\cdots ,b_m)$，其中 $a_1,a_2,\cdots ,a_n,b_1,b_2,\cdots ,b_m\in A$。在字典序下，$S\le T$ 当且仅当以下两条中的一条成立：

• 存在 $0\le k<\min \{n,m\}$ 使得对任意 $i\in \{1,2,\cdots ,k\}$ 有 $a_i=b_i$，但 $a_{k+1}<b_{k+1}$；
• 对任意 $i\in \{1,2,\cdots ,\min \{n,m\}\}$ 有 $a_i=b_i$，且 $n\le m$。

不难看出，对任意两个由 $A$ 中元素组成的有限数列 $S,T$，总有 $S\le T\vee T\le S$。也就是说，字典序是全序。

引理

PrSS 表达式展开时，字典序变小。

证明

设 $S=(a_1,a_2,\cdots ,a_n)$ 是 PrSS 表达式。

如果 $a_n=0$，则 $S$ 的展开式为 $T=(a_1,a_2,\cdots ,a_{n-1})$。根据定义，对任意 $i\in \{1,2,\cdots ,n-1\}$ 有 $a_i=a_i$，且 $n-1<m$，所以 $T<S$。

如果 $a_n\ne 0$，且展开式 $T$ 是 $S$ 的基本列的第 $0$ 项，则 $T$ 相当于删去 $S$ 的末项，所以 $T<S$。

如果 $a_n\ne 0$，且展开式 $T$ 是 $S$ 的基本列的第 $k>0$ 项，则 $T$ 相当于删去 $S$ 的末项，并复制若干次坏部。因为坏部的第一项（坏根）小于末项，所以 $T<S$。

证毕。

现在可以给出 PrSS 标准式的必要条件了。

临时定义（PrSS 规范式）

对表达式 $S=(a_1,a_2,\cdots ,a_n)$ 的长度 $n$ 归纳定义。

若 $n=0$，则 $S=()$ 是 PrSS 规范式。

若 $n>0$ 且 $S$ 中仅有首项是零，则 $S$ 是 PrSS 规范式当且仅当 $(a_2-1,a_3-1,\cdots ,a_n-1)$ 是 PrSS 规范式。

若 $n>0$ 且 $S$ 中有 $r>1$ 项是零，设 $a_{k_1}=a_{k_2}=\cdots =a_{k_r}=0$，其中 $1=k_1<k_2<\cdots <k_r<k_{r+1}=n+1$，令 $S_i=(a_{k_i},a_{k_i+1},\cdots ,a_{k_{i+1}-1})$。则 $S$ 是 PrSS 规范式当且仅当 $S_1,S_2,\cdots ,S_r$ 都是 PrSS 规范式且按字典序 $S_1\ge S_2\ge \cdots \ge S_r$。

PrSS 规范式是本文临时定义的，并不是通用术语。PrSS 规范式实际上等价于 PrSS 标准式。

定理

PrSS 标准式都是 PrSS 规范式。

证明

不难看出 PrSS 极限基本列都是 PrSS 规范式，因此只需证明 PrSS 规范式的展开式也是 PrSS 规范式即可。

对规范表达式 $S=(a_1,a_2,\cdots ,a_n)$ 的长度 $n$ 归纳证明。

$n=0,1$ 的情况是平凡的，下面讨论 $n>1$ 的情况。

若 $S$ 中有 $r>1$ 项是零，设 $a_{k_1}=a_{k_2}=\cdots =a_{k_r}=0$，其中 $1=k_1<k_2<\cdots <k_r<k_{r+1}=n+1$，令 $S_i=(a_{k_i},a_{k_i+1},\cdots ,a_{k_{i+1}-1})$。则 $S$ 的展开相当于 $S_r$ 的展开。根据归纳假设，$S_r$ 的展开式是规范的。因为 $S_r$ 展开后字典序会变小（引理），所以 $S$ 展开后，各部分的字典序依然递减，所以 $S$ 的展开式是规范的。注意这里要讨论 $S_r$ 的展开式有不止一个零的情况，不过这个讨论并不难，感兴趣的读者可以自行讨论。

若 $S$ 中仅有一项是零，且 $a_n=1$。令 $T_1=(a_2-1,a_3-1,\cdots ,a_n-1)$。因为 $S$ 是规范表达式，根据规范表达式的定义，$T_1$ 也是规范表达式。从规范表达式的定义中不难看出，去掉 $T_1$ 末尾的 $a_n-1=0$ 后依然是规范的，即 $T_2=(a_2-1,a_3-1,\cdots ,a_{n-1}-1)$ 规范。所以 $T=(a_1,a_2,\cdots ,a_{n-1})$ 规范。注意到 $S$ 的展开式形如 $(T,T,\cdots ,T)$，所以 $S$ 的展开式是规范的。

若 $S$ 中仅有一项是零，且 $a_n\ne 1$。令 $T=(a_2-1,a_3-1,\cdots ,a_n-1)$。因为 $S$ 规范，所以 $T$ 规范。根据归纳假设，$T$ 的展开式是规范的。设 $S$ 的一个展开式是 $(b_1,b_2,\cdots ,b_m)$，则由 PrSS 展开规则可知 $(b_2-1,b_3-1,\cdots ,b_m-1)$ 是 $T$ 的展开式，是规范的，所以 $S$ 的展开式也是规范的。

证毕。

在第一节证明 PrSS 没有无穷降链时，我们使用了序数的良序性。如果想不依赖序数就证明 PrSS 没有无穷降链，参见知乎用户 www620 的证明。这个证明依赖本节的两个结论：PrSS 表达式展开时字典序变小、PrSS 标准式都是规范式。注意到本节的两个结论不依赖第一节，所以没有循环论证的问题。

PrSS 标准式集的良序性

上一节我们证明了 PrSS 合法表达式在展开过程中字典序变小，并由此得到了 PrSS 标准式的必要条件。这一节，我们证明字典序变小反过来也意味着可以展开得到，并由此得到 PrSS 标准式的充分条件。

定理

设 $S,T$ 是 PrSS 规范式，且按字典序 $S<T$，则 $S$ 经过若干次展开可以得到 $T$。

注意上一节的引理对任意 PrSS 合法式均成立，而这个定理要求 $S,T$ 都是规范式。

证明

定义一种特殊的展开函数 $E$：设 PrSS 表达式 $U$ 的基本列为 $U_0,U_1,U_2,\cdots$。若存在 $i$ 使得按字典序 $U_i\ge S$，则取 $k=\min \{i\mid U_i\ge S\}$ 并定义 $E(U)=U_k$。如果对任意 $i$ 都有按字典序 $U_i<S$，则取 $E(U)=U$。如果 $U$ 是后缀表达式，则取 $U_0=U_1=\cdots$ 为 $U$ 的前驱表达式。特殊地，如果 $U$ 是零表达式，则 $E(U)=U$。

从 $E$ 的定义不难看出，如果按字典序 $U\ge S$，则按字典序 $E(U)\ge S$。令 $T_0=T$，$T_{n+1}=E(T_n)$。因为按字典序 $T>S$，所以对任意 $i$ 都有按字典序 $T_i\ge S$。

而第一节已经证明 PrSS 不存在无穷降链，所以存在 $k$ 使得 $T_k=T_{k+1}=\cdots$。讨论一下不难得到，这时有两种可能：

• $T_k=S$。
• 按字典序 $T_k>S$，但 $T_k$ 的基本列的每一项都按字典序小于 $S$。进一步讨论还可以看出，这种情况下 $T_k$ 一定是极限表达式。

前一种情况命题已经成立，只需要用反证法证明后一种情况不存在即可。

若存在，设 $T_k$ 的好部是 $G$，坏部是 $B$，末项是 $L$，坏根是 $L-1$，则 $T_k=(G,B,L)$，而 $T_k$ 的展开式形如 $(G,B,B,\cdots )$。

如果 $S$ 按字典序小于 $T_k$ 而大于 $(G,B,B,\cdots )$，那么 $S$ 一定以 $(G,B)$ 开头。设 $S=(G,B,X)$，那么 $X$ 的首项等于坏根 $L-1$，而 $X$ 按字典序大于 $(B,B,\cdots )$。

这与 $S$ 是规范表达式相矛盾。这个矛盾可以更明确地写出来，但会占据大量篇幅且可能不会提供新的见解，所以在此略。也许以后我会补充。

证毕。

至此，我们已经证明了，规范表达式集上由展开定义的序，等价于字典序。

定理

PrSS 规范式都是 PrSS 标准式。

证明

设 $S$ 是 PrSS 规范式。存在 $n$ 使得 $T=(0,1,2,\cdots ,n-1)$ 按字典序大于 $S$。根据上一个定理，$T$ 可以展开成 $S$，所以 $S$ 是 PrSS 标准式。

证毕。

至此，我们证明了 PrSS 没有无穷降链、PrSS 标准式集的序是字典序，而字典序是全序，所以 PrSS 标准式集上的序是良序。

但我们不止于此。下一节，我们要证明 PrSS 标准式集序同构于 ${\epsilon }_0$。

PrSS 标准式集的序型

为了证明 PrSS 标准式集序同构于 ${\epsilon }_0$，我们要证明第一节定义的保序映射 $F$ 是 PrSS 标准式集和 ${\epsilon }_0$ 之间的双射，结合 PrSS 标准式集的全序性，就能说明 $F$ 是 PrSS 标准式集和 ${\epsilon }_0$ 之间的序同构。

定理

$F$是 PrSS 标准式集与${\epsilon }_0$之间的保序双射。

证明

对于小于${\epsilon }_0$的序数$\alpha$，定义$Seq(\alpha )=(a_1,a_2,\cdots ,a_k)$是这样的自然数序列：

• $Seq(0)=()$为空序列
• $\alpha >0$时，设它的康托范式为$\alpha ={\omega }^{{\alpha }_1}+{\omega }^{{\alpha }_2}+{\omega }^{{\alpha }_3}+\cdots +{\omega }^{{\alpha }_n}$，则$Seq(\alpha )=T(S^{\prime }({\alpha }_1),S^{\prime }({\alpha }_2),\cdots ,S^{\prime }({\alpha }_n))$，其中$T$为序列的拼合，而如果$Seq(\alpha )=(a_1,a_2,\cdots ,a_k)$，$S^{\prime }(\alpha )$定义为$(0,a_1+1,a_2+1,\cdots ,a_k+1)$

我们给出几个引理：

引理 1 如果${\epsilon }_0>\alpha \ge \beta$，则按字典序$Seq(\alpha )\ge Seq(\beta )$

引理 2 $Seq(\alpha )$是 PrSS 的规范式。

引理 3 $F(Seq(\alpha ))=\alpha$

引理 4 $Seq(F(S))=S$，其中$S$为 PrSS 规范式

引理 1 的证明 取出所有有序对$(\alpha ,\beta )$使${\epsilon }_0>\alpha >\beta$但按字典序$Seq(\alpha )\le Seq(\beta )$，取出其中$\alpha$最小的一组。写出它们的康托范式：

$\alpha ={\omega }^{{\alpha }_1}+{\omega }^{{\alpha }_2}+{\omega }^{{\alpha }_3}+\cdots +{\omega }^{{\alpha }_p}$

$\beta ={\omega }^{{\beta }_1}+{\omega }^{{\beta }_2}+{\omega }^{{\beta }_3}+\cdots +{\omega }^{{\beta }_q}$

则以下两点成立其一：

1. 存在某个$i\le min\{p,q\}$使${\alpha }_i>{\beta }_i$
2. $q<p$，且对于所有$i\le q$有${\alpha }_i={\beta }_i$

对于前者，由于${\alpha }_i<\alpha$，根据$\alpha$的最小性，字典序下$Seq({\alpha }_i)>Seq({\beta }_i)$，根据定义，字典序下$Seq(\alpha )>Seq(\beta )$，矛盾。

对于后者，易知$Seq({\beta }_i)$是$Seq({\alpha }_i)$删去后面数项得到的子序列。故字典序下$Seq(\alpha )>Seq(\beta )$，矛盾。

因此，这样的有序对$(\alpha ,\beta )$不存在，所以如果${\epsilon }_0>\alpha \ge \beta$，则按字典序$Seq(\alpha )\ge Seq(\beta )$

又如果${\epsilon }_0>\alpha =\beta$，则按字典序$Seq(\alpha )=Seq(\beta )$。于是引理1得证。

引理 2 的证明 设$\alpha <{\epsilon }_0$是最小使得$Seq(\alpha )$不是 PrSS 的规范式的序数。设它的康托范式为$\alpha ={\omega }^{{\alpha }_1}+{\omega }^{{\alpha }_2}+{\omega }^{{\alpha }_3}+\cdots +{\omega }^{{\alpha }_n}$。

(1) 若$n=1$，$\alpha ={\omega }^{{\alpha }_1}$，$Seq(\alpha )=S^{\prime }({\alpha }_1)$。根据定义，$Seq(\alpha )$是 PrSS 的规范式当且仅当$Seq({\alpha }_1)$是 PrSS 的规范式，而${\alpha }_1<\alpha$，根据最小性，$Seq({\alpha }_1)$是 PrSS 的规范式，故$Seq(\alpha )$也是 PrSS 的规范式，矛盾。

(2) 若$n>1$，$\alpha ={\omega }^{{\alpha }_1}+{\omega }^{{\alpha }_2}+{\omega }^{{\alpha }_3}+\cdots +{\omega }^{{\alpha }_n}$，$Seq(\alpha )=T(S^{\prime }({\alpha }_1),S^{\prime }({\alpha }_2),\cdots ,S^{\prime }({\alpha }_n))$。根据定义，$Seq(\alpha )$是 PrSS 的规范式当且仅当每个$Seq({\alpha }_k)$均是 PrSS 的规范式且$Seq({\alpha }_k)$的字典序不增，$k=1,2,\cdots ,n$。前者是显然的(类似于上文的(1)部分)，而后者由${\alpha }_1\ge {\alpha }_2\ge \cdots {\alpha }_n$和引理1保证。于是$Seq(\alpha )$是 PrSS 的规范式，矛盾。

故这样的$\alpha <{\epsilon }_0$不存在。引理2得证。

引理 3 的证明 设$\alpha <{\epsilon }_0$是最小的不满足$F(Seq(\alpha ))=\alpha$的序数。它的康托范式为$\alpha ={\omega }^{{\alpha }_1}+{\omega }^{{\alpha }_2}+{\omega }^{{\alpha }_3}+\cdots +{\omega }^{{\alpha }_n}$。

则有$Seq(\alpha )=T(S^{\prime }({\alpha }_1),S^{\prime }({\alpha }_2),\cdots ,S^{\prime }({\alpha }_n))$。根据定义，$F(T(S^{\prime }({\alpha }_1),S^{\prime }({\alpha }_2),\cdots ,S^{\prime }({\alpha }_n)))=F(S^{\prime }({\alpha }_1))+F(S^{\prime }({\alpha }_2))+\cdots +F(S^{\prime }({\alpha }_n))={\omega }^{F(Seq({\alpha }_1))}+{\omega }^{F(Seq({\alpha }_2))}+\cdots +{\omega }^{F(Seq({\alpha }_n))}$，而${\alpha }_k<\alpha$，$k=1,2,\cdots ,n$，根据最小性，$F(Seq({\alpha }_k))={\alpha }_k$，故$F(T(S^{\prime }({\alpha }_1),S^{\prime }({\alpha }_2),\cdots ,S^{\prime }({\alpha }_n)))={\omega }^{{\alpha }_1}+{\omega }^{{\alpha }_2}+{\omega }^{{\alpha }_3}+\cdots +{\omega }^{{\alpha }_n}=\alpha$。矛盾。

故这样的$\alpha <{\epsilon }_0$不存在。引理3得证。

引理 4 的证明 若对于某个 PrSS 规范式$S$有$Seq(F(S))>S$，则由引理1得$F(Seq(F(S))>F(S)$，由引理3得$F(S)>F(S)$，矛盾。同理，$Seq(F(S))<S$则$F(S)<F(S)$，矛盾。故$Seq(F(S))=S$。

定理的证明 由引理1~4，$F$有逆映射$Seq$，且$Seq$保序。于是$Seq$(和其逆$F$)是 PrSS 标准式集与${\epsilon }_0$之间的序同构。

证毕。

---

在下面，我们介绍另外一种 PrSS 良序性的证法。

证明

我们将使用 $E$ 表示空序列，使用 $⌢$ 表示序列的连接。

对于序列 $S$ ，我们将使用长度 $(S)$ 表示序列 $S$ 的长度，使用 $S_n(n<\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(S))$ 表示 $S$ 的第 $n$ 项，使用 $S_{◻}$ 表示 $S$ 的最后一项，使用 $S^{+}$ 表示对 $S$ 的每个分量加 1 得到的序列。

对于序列 $S$ 和自然数 $m,n$ ，且 $m\le n\le$ 长度 $(S)$ ，设 $\mathrm{sub}(S,m,n)$ 为唯一序列 $T$ ，且$T_x=S_{m+x}$ （若 $x<n-m$ ）且长度 $(T)=n-m$ 。

定义 1 递归地定义 $P$ ，一组有限长度的自然数序列，如下所示。

$P_0:=\{E\},$

$P_{n+1}:=P_n\cup \{S⌣(0)⌣T^{+}\mid S\in P_n\wedge T\in P_n\},$

$P:=\bigcup _{n\in \mathbb{\mathbb{N}}}{P}_n.$

定理 1 $P$ 具有如下性质：

(1) 对于 $P$ 中的任意元素 $S$ ， $S=E$ 或 $S_0=0$ 。

(2) 对于 $P$ 中的任意元素 $A,B,C,D$ ，若 $A⌢(0)⌢B^{+}=C⌢(0)⌢D^{+}$ ，则 $A=C$ 且 $B=D$ 。

证明：

1. 运用结构归纳法，构造 $P$ 来证明。

如果 $S=E$ ，则 $S=E$ 或 $S_0=0$ 当然成立。假设存在 $(s,t)\in P^2$ ，使得 $S=s⌢(0)⌢t^{+},$ 且两者均满足条件。如果 $s=E$ ，则 $S=s⌢(0)⌢t^{+}=E⌢(0)⌢t^{+}=(0)⌢t^{+},$ 因此 $S_0=0$ 。如果 $s_0=0$ ，则 $S=s⌢(0)⌢t^{+},$ 因此 $S_0=0$ 。结构归纳表明，对于 $P$ 的任何元素 $S$ ， $S=E$ 或“ $S$ 的第一个项为 0”。

2. 证明逆否命题。换句话说，由于 $A\ne C$ 或 $B\ne D$ ，我们证明 $A⌢(0)⌢B^{+}\ne C⌢(0)⌢D^{+}.$ 如果 $A\ne C$ ，则长度 $(A)\ne \mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(C)$ ，或者存在 $n<\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(A)$ ，使得 $A_n\ne C_n$ 。如果长度 $(A)\ne \mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(C)$ ，则（不失一般性，令长度 $(A)<\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(C),$ ）$(C⌢(0)⌢D^{+}{)}_{\text{length}(C)}=((0)⌢D^{+}{)}_0=0.$ 然而，

$\begin{array}{l}(A⌢(0)⌢B^{+}{)}_{\text{length}(C)}\\ ={(\left(0\right)⌢B^{+})}_{\text{length}(C)-\text{length}(A)}\\ =B_{\text{length}(C)-\text{length}(A)-1}^{+}>0,\\ \end{array}$

所以 length(C) 项不匹配，因此 $A⌢(0)⌢B^{+}\ne C⌢(0)⌢D^{+}.$ 如果存在 $n<\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(A)$ 使得 $A_n\ne C_n$ ，则对于 $n$ ，$(A⌢(0)⌢B^{+}{)}_n\ne (C⌢(0)⌢D^{+}{)}_n,$ 因此 $A⌢(0)⌢B^{+}\ne C⌢(0)⌢D^{+}.$ 如果 $A=C$ 且 $B\ne D$ ，则 $A⌢(0)⌢B^{+}=C⌢(0)⌢B^{+}\ne C⌢(0)⌢D^{+}.$ 因此，如果 $A\ne C$ 或 $B\ne D$ ，则 $A⌢(0)⌢B^{+}\ne C⌢(0)⌢D^{+}.$

$P$ 是由 $E$ 和函数 $(A,B)\mapsto A\sim (0)\sim B^{+}$ 生成的函数，上述定理断言它是自由生成的（ $P$ 的一个元素不能用两种不同的方式表示）。由于它是下面证明中的一个重要函数，我们将其缩写为 $\mathrm{gen}(A,B):=A⌢(0)⌢B^{+}.$

定义 2 函数 expand $:(P\mathrm{\setminus }\{E\})\times \mathbb{\mathbb{N}}arrow\mathbb{\mathbb{N}}<\omega$ 定义如下。注意，定义域中的元素 $S$ 不为空，因此 $S_{\perp }$ 有定义。

(1) 如果 $S_{\perp }=0$ ，则 $\mathrm{expand}(S):=\mathrm{sub}(S,0,\mathrm{length}(S)-1).$

(2) 如果 $S_{\perp }>0$ ，则（根据引理 1.1.）$0\in \{i\in \mathbb{\mathbb{N}}\mid i<\mathrm{length}(S)\wedge S_i<S_{◻}\},$ 因此 $\{i\in \mathbb{\mathbb{N}}\mid i<\mathrm{length}(S)\wedge S_i<S_{◻}\}$ 非空。

定义 $\mathrm{br}(S):=\max \{i\in \mathbb{\mathbb{N}}\mid i<\mathrm{length}(S)\wedge S_i<S_{◻}\},$ $\mathrm{gp}(S):=\mathrm{sub}(S,0,\mathrm{br}(S)),$ $\mathrm{bp}(S):=\mathrm{sub}(S,\mathrm{br}(S),\mathrm{length}(S)-1),$ $\mathrm{expand}(S):=\mathrm{gp}(S)⌣\underset{n}{\underbrace{\mathrm{bp}(S)⌣\cdots ⌣\mathrm{bp}(S)}}.$

定理 2 (1) 对于任意 $A\in P$ ，$\mathrm{expand}(\mathrm{gen}(A,E),n)=A.$

(2) 对于任意 $(A,B)\in P^2$ ，$\mathrm{expand}(\mathrm{gen}(A,\mathrm{gen}(B,E)),n)=A⌢\underset{n}{\underbrace{(0)⌢B^{+}⌢\cdots ⌢(0)⌢B^{+}}}.$

(3) 对于任意的 $(A,B,C)\in P^2\times (P\mathrm{\setminus }\{E\})$ ，$\mathrm{expand}(\mathrm{gen}(A,\mathrm{gen}(B,C)),n)=\mathrm{gen}(A,\mathrm{expand}(\mathrm{gen}(B,C),n)).$

证明：1. 若 $S:=\mathrm{g}\mathrm{e}\mathrm{n}(A,E)$ ，则 $S=A⌢(0)⌢E^{+}=A⌢(0).$ 故 $S_{\perp }=0$ 。因此 $\mathrm{expand}(S,n)=\mathrm{sub}(S,0,\mathrm{length}(S)-1)=A.$

2. 若 $S:=\mathrm{gen}(A,\mathrm{gen}(B,E)),$ 则 $S=A⌢(0)⌢(B⌢(0)⌢E^{+}{)}^{+}=A⌢(0)⌢B^{+}⌢(1).$ 因此， $S_{\perp }=1>0$

$\begin{array}{l}\mathrm{br}(S)=\max \{i\in \mathbb{\mathbb{N}}\mid i<\mathrm{length}(S)\wedge S_i<S_{◻}\}\\ =\max \{i\in \mathbb{\mathbb{N}}\mid i<\mathrm{length}(S)\wedge S_i<1\}\\ =\max \{i\in \mathbb{\mathbb{N}}\mid i<\mathrm{length}(S)\wedge S_i=0\}.\\ \end{array}$

这里，由于 $S_{\mathrm{l}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}(A)}=0$ ，因此 $\mathrm{length}(A)\in \{i\in \mathbb{\mathbb{N}}\mid i<\mathrm{length}(S)\wedge S_i=0\}.$ 另外，对于任意 $n>$ length $(S)$ ，$S_n={(B^{+}⌢(1))}_{n-\text{length}(S)-1}=1+{(B⌢(0))}_{n-\text{length}(S)-1}>0$ 所以 $n\in \{i\in \mathbb{\mathbb{N}}\mid i<\mathrm{length}(S)\wedge S_i=0\}.$ 因此，$\mathrm{br}(S)=\max \{i\in \mathbb{\mathbb{N}}\mid i<\mathrm{length}(S)\wedge S_i=0\}=\mathrm{length}(A).$ 在这种情况下

$\begin{array}{l}\mathrm{gp}(S)=\mathrm{sub}(S,0,\mathrm{br}(S))\\ =\mathrm{sub}(A⌢(0)⌢B^{+}⌢(1),0(A))\\ =A.\\ \end{array}$

此外，

$\begin{array}{l}\mathrm{bp}(S)=\mathrm{sub}(S,\mathrm{br}(S),\mathrm{length}(S)-1)\\ =\mathrm{sub}(A⌣(0)⌣B^{+}⌣(1),\text{length}(A),\text{length}.(S)-1)\\ =(0)⌢B^{+}.\\ \end{array}$

因此 $\mathrm{expand}(S,n)=A⌢\underset{n}{\underbrace{(0)⌢B^{+}⌢\cdots ⌢(0)⌢B^{+}}}.$

3. 若 $S:=\mathrm{gen}(A,\mathrm{gen}(B,C)),$ 则

$\begin{array}{l}S=A⌢(0)⌢(B⌢(0)⌢C^{+}{)}^{+}\\ =A⌢(0)⌢B^{+}⌢(1)⌢C^{++}.\\ \end{array}$

由于 $C\ne E$ ，$S_{◻}=C_{◻}^{++}=C_{◻}+2>1.$ 又由于 $S_{\text{length}(A)+1+\text{length}(B)}=1,$ $\mathrm{length}(A)+1+\mathrm{length}(B)\in \{i\in \mathbb{\mathbb{N}}\mid i<\mathrm{length}(S)\wedge S_i<S_{◻}\}.$ 特别地，

$\begin{array}{l}\mathrm{br}(S)=\max \{i\in \mathbb{\mathbb{N}}\mid i<\mathrm{length}(S)\wedge S_i<S_{◻}\}\\ \ge \mathrm{length}(A)+1+\mathrm{length}(B).\\ \end{array}$

令 $r:=\ker (S)$ ，则

$\begin{array}{l}\mathrm{br}(B⌢(0)⌢C^{+})\\ =\max \{i\in \mathbb{\mathbb{N}}\mid i<\mathrm{length}(B⌢(0)⌢C^{+})\\ \wedge (B⌣(0)⌣C^{+}{)}_i<(B⌣(0)⌣C^{+}{)}_{◻}\}.\\ \end{array}$

由于 $\mathrm{length}(A)+1+\mathrm{length}(B⌢(0)⌢C^{+})=\mathrm{length}(S),$ 我们有 $S_{\text{length}(A)+1+i}={(B⌢(0)⌢C^{+})}_i-1,$ 且 $S_{◻}=(B⌢(0)⌢C^{+}{)}_{◻}-1,$

$\begin{array}{l}\{i\in \mathbb{\mathbb{N}}\mid i<\mathrm{length}(B⌢(0)⌢C^{+})\\ \wedge (B⌢(0)⌢C^{+}{)}_i<(B⌢(0)⌢C^{+})◻\}\\ =\{i\in \mathbb{\mathbb{N}}\mid \mathrm{length}(A)+1+i<\mathrm{length}(S)\wedge S_{\text{length}(A)+1+i}.\\ \end{array}$

因此

$\begin{array}{l}\mathrm{br}(B⌣(0)⌣C^{+})\\ =\max \{i\in \mathbb{\mathbb{N}}\mid i<\text{length}(B⌢(0)⌢C^{+})\\ \wedge (B⌣(0)⌣C^{+}{)}_i<(B⌣(0)⌣C^{+}{)}_{◻}\}\\ =r-\mathrm{length}(A)-1.\\ \end{array}$

因此，$\mathrm{gp}(B\sim (0)\sim C^{+})=\mathrm{sub}(B\sim (0)\sim C^{+},0,r-\mathrm{length}(A)-1),$ 所以

$\begin{array}{l}\mathrm{g}\mathrm{p}(B⌣(0)⌣C^{+}{)}^{+}\\ =\mathrm{sub}({(B⌢(0)⌢C^{+})}^{+},0,r-\text{length}.(A)-1)\\ =\mathrm{sub}(S\mathrm{length}(A)+1,r).\\ \end{array}$

另外，由于

$\begin{array}{l}\mathrm{b}\mathrm{p}(B⌢(0)⌢C^{+})=\mathrm{sub}(B⌢(0)⌢C^{+},\\ r-\text{length}(A)-1,\text{length}(B⌣(0)⌣C^{+})),\\ \end{array}$

我们有

$\begin{array}{l}\mathrm{b}\mathrm{p}(B⌣(0)⌣C^{+}{)}^{+}\\ =\mathrm{sub}({(B⌢(0)⌢C^{+})}^{+},r-\text{length}(A)-1,\text{length}(B⌢(0)⌢C^{+})-1)\\ =\mathrm{sub}(S,r,\text{length}(S)-1{)}^{-}.\\ \end{array}$

此外 $\mathrm{gp}(S)=\mathrm{sub}(S,0,r),\mathrm{bp}(S)=\mathrm{sub}(S,r,\text{length}(S)-1),$ 因此

$\begin{array}{l}\mathrm{expand}(B⌣(0)⌣C^{+},n{)}^{+}\\ =\mathrm{g}\mathrm{p}(B⌢(0)⌢C^{+}{)}^{+}⌢\\ \underset{n}{\underbrace{\mathrm{bp}{(B⌢(0)⌢C^{+})}^{+}⌢\cdots ⌢\mathrm{bp}{(B⌢(0)⌢C^{+})}^{+}}}\\ =\mathrm{sub}(S,\mathrm{length}(A)+1,r)⌢\underset{n}{\underbrace{\mathrm{bp}(S)⌢\cdots ⌢\mathrm{bp}(S)}}.\\ \end{array}$

于是我们得到

$\begin{array}{l}\mathrm{expand}(S,n)\\ =\mathrm{sub}(S,0,r)⌣\underset{n}{\underbrace{\mathrm{b}\mathrm{p}(S)⌣\cdots ⌣\mathrm{b}\mathrm{p}(S)}}\\ =A⌢(0)\curvearrowleft \mathrm{sub}(S,\mathrm{length}(A)+1,r)\curvearrowleft \underset{n}{\underbrace{\mathrm{bp}(S)\curvearrowleft \cdots {\mathrm{bp}}^{}}}\\ =A⌣(0)⌣\mathrm{expand}(B⌣(0)⌣C^{+},n{)}^{+}.\\ \end{array}$

证毕。

定理 3 对于任意 $S\in P$ 和 $n\in \mathbb{\mathbb{N}}$ ， $S=E$ 或 $\mathrm{expand}(S,n)\in P$ 。

证明：使用结构归纳法构造 $P$ 。

$S=E$ 的情况是平凡的。假设存在 $(T,U)\in P^2$ 使得 $S=\mathrm{g}\mathrm{e}\mathrm{n}(T,U)$ ，并且两者都满足条件。如果 $U=E$ ，则根据引理 2.1，展开 $(S,n)=T\in P$ 。从这里开始，假设存在 $(V,W)\in P^2$ 使得 $U=\mathrm{g}\mathrm{e}\mathrm{n}(V,W)$ ，并且两者都满足条件。如果 $W=E$ ，则根据引理 2.2 $S=\mathrm{gen}(T,\mathrm{gen}(V,E)).$ 因此 $\mathrm{expand}(S,n)=T⌢\underset{n}{\underbrace{(0)⌢V^{+}⌢\cdots ⌢(0)⌢V^{+}}}.$ 现在，利用数学归纳法，我们可以证明 $\mathrm{expand}(S,0)=T\in P$ 且 $\mathrm{expand}(S,k+1)=\mathrm{expand}(S,k)⌢(0)⌢V^{+}=\mathrm{gen}(\mathrm{expand}(S,k),V)$ 因此对于任何 $n\in \mathbb{\mathbb{N}}$ ，我们可以证明 $\mathrm{expand}(S,n)\in P$ 。如果 $W\ne E$ ，则 $S=\mathrm{gen}(T,\mathrm{gen}(V,W)).$ 因此 $\mathrm{expand}(S,n)=\mathrm{gen}(T,\mathrm{expand}(\mathrm{gen}(V,W),n))=\mathrm{gen}(T,\mathrm{expand}(U,n))\in P,$ 因此，对于任何 $S\in P$ ， $S=E$ 或 $\mathrm{expand}(S,n)\in P$ 。证毕。

引理 2 是根据 $P$ 的结构对 expand 的行为进行分类的一种方式。引理 3 表明 expand 的输出也是 $P$ 的一个元素。

通过对 $P$ 结构进行递归，定义映射 trans: $P\to {\epsilon }_0$ ，如下所示。注意， ${\epsilon }_0$ 是加法和 $\omega$ 运算下封闭的序数映射。

定义 3 (1) 如果 $S=E$ ，则 $\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{s}(S):=0$

(2) 如果存在 $(A,B)\in P^2$ 使得 $S=\mathrm{g}\mathrm{e}\mathrm{n}(A,B)$ ，则 $\mathrm{trans}(S):=\mathrm{trans}(A)+{\omega }^{\mathrm{trans}(B)}.$

定理 4 对于任意 $S\in P,n\in \mathbb{\mathbb{N}}$ ，都有 $S=E$ 或 $\mathrm{trans}(\mathrm{expand}(S,n))<\mathrm{trans}(S).$

证明：通过构造 $P$ 的结构归纳法来证明。

当 $S=E$ 时，这是平凡的。从现在开始，假设 $(T,U)\in P^2$ 存在，使得 $S=\mathrm{g}\mathrm{e}\mathrm{n}(T,U)$ ，并且两者都满足条件。如果 $U=E$ ，则 $S=\mathrm{g}\mathrm{e}\mathrm{n}(T,E)$ ，因此根据引理 2.1， $\mathrm{expand}(S,n)=T$ 。因此

$\begin{array}{l}(\mathrm{expand}(S,n))\\ =\mathrm{trans}(T)<\mathrm{trans}(T)+{\omega }^0\\ =\mathrm{trans}(T)+{\omega }^{\text{trans}}(E)\\ =\mathrm{trans}(\mathrm{gen}(T,E))\\ =\mathrm{trans}(S).\\ \end{array}$

从现在开始，我们假设 $(V,W)\in P^2$ 存在，使得 $U=\mathrm{g}\mathrm{e}\mathrm{n}(V,W)$ 且两者都满足条件。如果 $W=E$ ，则 $S=\mathrm{gen}(T,\mathrm{gen}(V,E)),$ 因此

$\begin{array}{l}\mathrm{trans}(S))\\ =\mathrm{trans}(\mathrm{gen}(T,\mathrm{gen}(V,E))))\\ =\mathrm{trans}(T)+{\omega }^{\mathrm{trans}(\mathrm{g}\mathrm{e}\mathrm{n}(V,E))})\\ =\mathrm{trans}(T)+{\omega }^{\mathrm{trans}(V)+{\omega }^{\mathrm{trans}(E)}}\\ =\mathrm{trans}(T)+{\omega }^{\mathrm{trans}(V)+1}.\\ \end{array}$

另外，根据引理 2.2，$\mathrm{expand}(S,n)=T⌢\underset{n}{\underbrace{(0)⌢V^{+}⌢\cdots ⌢(0)⌢V^{+}}}.$ 通过数学归纳法，我们可以证明$\mathrm{trans}(\mathrm{expand}(S,n))=\mathrm{trans}(T)+{\omega }^{\mathrm{trans}(V)}\times n.$ 因此对于任意 $n\in \mathbb{\mathbb{N}}$ ，$\mathrm{trans}(\exp (S,n))=\mathrm{trans}(T)+{\omega }^{\mathrm{trans}(V)}\times n<\mathrm{trans}(T)+{\omega }^{\mathrm{trans}(V)+1}=\mathrm{trans}(S).$ 若 $W\ne E$ ，则根据引理 2.3 $\mathrm{expand}(S,n)=\mathrm{gen}(T,\mathrm{expand}(U,n).$ 由于 $U$ 满足 $\mathrm{trans}(\mathrm{expand}(U,n))<\mathrm{trans}(U)$ 因此

$\begin{array}{l}\mathrm{trans}(\mathrm{expand}(S,n))\\ =\mathrm{trans}(\mathrm{gen}(T,\text{expand}(U,n)))\\ =\mathrm{trans}(T)+{\omega }^{\mathrm{trans}(\exp (U,n))}\mathrm{trans}(T)+{\omega }^{\mathrm{trans}(U)}\\ =\mathrm{trans}(S).\\ \end{array}$

因此，对于任意的 $S\in P,n\in \mathbb{\mathbb{N}}$ ，都有 $S=E$ 或 $\mathrm{trans}(\exp \mathrm{a}\mathrm{n}\mathrm{d}(S,n))<\mathrm{trans}(S)$ 。证毕。

定理 5 对于任意 $S\in P,a:\mathbb{\mathbb{N}}\mathbb{\mathbb{N}}$ ，都存在 $k\in \mathbb{\mathbb{N}}$ 使得 $S\left[a_0\right]\left[a_1\right]\dots \left[a_{k-1}\right]=E.$

证明：假设这样的 $k\in \mathbb{\mathbb{N}}$ 不存在。对于每个 $k\in \mathbb{\mathbb{N}}$ ，都有 $S\left[a_0\right]\left[a_1\right]\dots \left[a_{k-1}\right]\ne E,$ 因此 $\mathrm{trans}(S[a_0][a_1]\dots [a_{k-1}])\ne 0.$ 因此，如果 $S\left[a_0\right]\left[a_1\right]\dots \left[a_{k-1}\right]$ 有定义，则 $S[a_0][a_1]\dots [a_{k-1}][a_k]$ 也有定义。根据数学归纳法，$S[a_0][a_1]\dots [a_{k-1}]$ 对于任意 $k\in \mathbb{\mathbb{N}}$ 都有定义。然而，根据引理 4，$\mathrm{trans}(S)>\mathrm{trans}\left(S\left[a_0\right]\right)>\mathrm{trans}\left(S\left[a_0\right]\left[a_1\right]\right)>\dots$ 这是一个无限递减的序数序列。这与序数的良序性相矛盾。矛盾的是，存在 $k\in \mathbb{\mathbb{N}}$ 使得 $S\left[a_0\right]\left[a_1\right]\dots \left[a_{k-1}\right]=E.$ 这意味着无论选择哪种函数，初等序列都会在有限次数的迭代后都会变成空序列并停止。由此我们证明了 PrSS 的停机性。