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 合法表达式在展开过程中字典序变小，并由此得到了 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 标准式集序同构于 ${\epsilon }_0$

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

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

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

【未完】