PrSS的良序性
更多操作
证明（zhy137036）
PrSS 没有无穷降链
首先我们将 PrSS 的每个合法表达式 \(S\) 对应于一个不超过 \(\varepsilon_0\) 的序数 \(F(S)\)。然后我们证明 PrSS 表达式展开时，其对应的序数严格递减。于是就可以依据 \(\varepsilon_0\) 的良序性说明 PrSS 没有无穷降链。
第一步：将 PrSS 的每个合法表达式对应于一个不超过 \(\varepsilon_0\) 的序数。
对 PrSS 表达式的长度归纳定义。
任取 PrSS 合法表达式 \(S=(a_1,a_2,\cdots,a_n)\)。
若 \(n=0\)，则 \(F(S)=0<\varepsilon_0\)。
若 \(n>0\)，分两种情况讨论：
- 若 \(\forall i\in\{2,3,\cdots,n\},a_i\neq 0\)，则取 \(T=(a_2-1,a_3-1,\cdots,a_n-1)\)。
不难验证，\(T\) 是合法的 PrSS 表达式，且 \(T\) 的长度比 \(S\) 的长度短。令 \(F(S)=\omega^{F(T)}\)。
因为 \(F(T)<\varepsilon_0\)，所以 \(F(S)<\varepsilon_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}),\quad 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)<\varepsilon_0\)，所以 \(F(S)<\varepsilon_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})\)。分为两种情况讨论：
- 若 \(\forall i\in\{2,3,\cdots,n\},a_i\neq 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}),\quad 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\neq 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}),\quad 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}),\quad i=1,2,\cdots,s\)，则 \(F(V_p)=F(T_1)+F(T_2)+\cdots+F(T_s)\)。
所以 \(\begin{aligned}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{aligned}\) - 若 \(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\neq 1\)。
令 \(T=(a_2-1,a_3-1,\cdots,a_n-1)\)，因为 \(a_n-1\neq 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\lor 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\neq 0\)，且展开式 \(T\) 是 \(S\) 的基本列的第 \(0\) 项，则 \(T\) 相当于删去 \(S\) 的末项，所以 \(T<S\)。
如果 \(a_n\neq 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\neq 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 的证明[1]。这个证明依赖本节的两个结论：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 标准式集序同构于 \(\varepsilon_0\)。
PrSS 标准式集的序型
为了证明 PrSS 标准式集序同构于 \(\varepsilon_0\)，我们要证明第一节定义的保序映射 \(F\) 是 PrSS 标准式集和 \(\varepsilon_0\) 之间的双射，结合 PrSS 标准式集的全序性，就能说明 \(F\) 是 PrSS 标准式集和 \(\varepsilon_0\) 之间的序同构。
定理
\(F\)是 PrSS 标准式集与\(\varepsilon_0\)之间的保序双射。
证明
对于小于\(\varepsilon_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'(\alpha_1),S'(\alpha_2),\cdots,S'(\alpha_n))\)，其中\(T\)为序列的拼合，而如果\(Seq(\alpha)=(a_1,a_2,\cdots,a_k)\)，\(S'(\alpha)\)定义为\((0,a_1+1,a_2+1,\cdots,a_k+1)\)
我们给出几个引理：
引理 1 如果\(\varepsilon_0>\alpha\geq\beta\)，则按字典序\(Seq(\alpha)\geq{Seq(\beta)}\)
引理 2 \(Seq(\alpha)\)是 PrSS 的规范式。
引理 3 \(F(Seq(\alpha))=\alpha\)
引理 4 \(Seq(F(S))=S\)，其中\(S\)为 PrSS 规范式
引理 1 的证明 取出所有有序对\((\alpha,\beta)\)使\(\varepsilon_0>\alpha>\beta\)但按字典序\(Seq(\alpha)\leq{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}\)
则以下两点成立其一：
- 存在某个\(i\leq{min\{p,q\}}\)使\(\alpha_i>\beta_i\)
- \(q<p\)，且对于所有\(i\leq{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)\)不存在，所以如果\(\varepsilon_0>\alpha\geq\beta\)，则按字典序\(Seq(\alpha)\geq{Seq(\beta)}\)
又如果\(\varepsilon_0>\alpha=\beta\)，则按字典序\(Seq(\alpha)=Seq(\beta)\)。于是引理1得证。
引理 2 的证明 设\(\alpha<\varepsilon_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'(\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'(\alpha_1),S'(\alpha_2),\cdots,S'(\alpha_n))\)。根据定义，\(Seq(\alpha)\)是 PrSS 的规范式当且仅当每个\(Seq(\alpha_k)\)均是 PrSS 的规范式且\(Seq(\alpha_k)\)的字典序不增，\(k=1,2,\cdots,n\)。前者是显然的(类似于上文的(1)部分)，而后者由\(\alpha_1\geq\alpha_2\geq\cdots\alpha_n\)和引理1保证。于是\(Seq(\alpha)\)是 PrSS 的规范式，矛盾。
故这样的\(\alpha<\varepsilon_0\)不存在。引理2得证。
引理 3 的证明 设\(\alpha<\varepsilon_0\)是最小的不满足\(F(Seq(\alpha))=\alpha\)的序数。它的康托范式为\(\alpha=\omega^{\alpha_1}+\omega^{\alpha_2}+\omega^{\alpha_3}+\cdots +\omega^{\alpha_n}\)。
则有\(Seq(\alpha)=T(S'(\alpha_1),S'(\alpha_2),\cdots,S'(\alpha_n))\)。根据定义，\(F(T(S'(\alpha_1),S'(\alpha_2),\cdots,S'(\alpha_n)))=F(S'(\alpha_1))+F(S'(\alpha_2))+\cdots+F(S'(\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'(\alpha_1),S'(\alpha_2),\cdots,S'(\alpha_n)))=\omega^{\alpha_1}+\omega^{\alpha_2}+\omega^{\alpha_3}+\cdots +\omega^{\alpha_n}=\alpha\)。矛盾。
故这样的\(\alpha<\varepsilon_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 标准式集与\(\varepsilon_0\)之间的序同构。
证毕。
在下面，我们介绍另外一种 PrSS 良序性的证法。
证明（pbot）
我们将使用 \(E\) 表示空序列，使用 \(\frown\) 表示序列的连接。
对于序列 \(S\) ，我们将使用长度 \(( S )\) 表示序列 \(S\) 的长度，使用 \(S_{n} ( n < \mathrm {length} ( S ) )\) 表示 \(S\) 的第 \(n\) 项，使用 \(S_{\square}\) 表示 \(S\) 的最后一项，使用 \(S^{+}\) 表示对 \(S\) 的每个分量加 1 得到的序列。
对于序列 \(S\) 和自然数 \(m ,n\) ，且 \(m \leq n \leq\) 长度 \(( S )\) ，设 \(\operatorname{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 \left\{S \smile (0) \smile T^{+} \mid S \in P_{n} \wedge T \in P_{n} \right\},\)
\(P :=\bigcup_ {n \in \mathbb {N}} P_{n}.\)
定理 1 \(P\) 具有如下性质：
(1) 对于 \(P\) 中的任意元素 \(S\) ， \(S=E\) 或 \(S_{0}=0\) 。
(2) 对于 \(P\) 中的任意元素 \(A ,B ,C ,D\) ，若 \(A \frown ( 0 ) \frown B^{+}=C \frown ( 0 ) \frown D^{+}\) ，则 \(A=C\) 且 \(B=D\) 。
证明：
1. 运用结构归纳法，构造 \(P\) 来证明。
如果 \(S=E\) ，则 \(S=E\) 或 \(S_{0}=0\) 当然成立。假设存在 \(( s ,t ) \in P^{2}\) ，使得 \(S=s \frown (0) \frown t^{+},\) 且两者均满足条件。如果 \(s=E\) ，则 \(S=s \frown (0) \frown t^{+}=E \frown (0) \frown t^{+}=(0) \frown t^{+},\) 因此 \(S_{0}=0\) 。如果 \(s_{0}=0\) ，则 \(S=s \frown (0) \frown t^{+},\) 因此 \(S_{0}=0\) 。结构归纳表明，对于 \(P\) 的任何元素 \(S\) ， \(S=E\) 或“ \(S\) 的第一个项为 0”。
2. 证明逆否命题。换句话说，由于 \(A \neq C\) 或 \(B \neq D\) ，我们证明 \(A \frown (0) \frown B^{+} \neq C \frown (0) \frown D^{+}.\) 如果 \(A \neq C\) ，则长度 \(( A ) \neq \mathrm {length} ( C )\) ，或者存在 \(n < \mathrm {length} ( A )\) ，使得 \(A_{n} \neq C_{n}\) 。如果长度 \(( A ) \neq \mathrm {length} ( C )\) ，则（不失一般性，令长度 \(( A ) < \mathrm {length} ( C ) ,\) ）\((C \frown (0) \frown D^{+})_{\text {length} (C)}=((0) \frown D^{+})_{0}=0.\) 然而，
\(\begin{array}{l} (A \frown (0) \frown B^{+})_{\text {length} (C)} \\=\left(\left(0\right) \frown B^{+}\right)_{\text {length} (C)-\text {length} (A)} \\=B_{\text {length} (C)-\text {length} (A)-1}^{+} > 0,\\ \end{array}\)
所以 length(C) 项不匹配，因此 \(A \frown (0) \frown B^{+} \neq C \frown (0) \frown D^{+}.\) 如果存在 \(n < \mathrm {length} ( A )\) 使得 \(A_{n} \neq C_{n}\) ，则对于 \(n\) ，\((A \frown (0) \frown B^{+})_{n} \neq (C \frown (0) \frown D^{+})_{n},\) 因此 \(A \frown (0) \frown B^{+} \neq C \frown (0) \frown D^{+}.\) 如果 \(A=C\) 且 \(B \neq D\) ，则 \(A \frown (0) \frown B^{+}=C \frown (0) \frown B^{+} \neq C \frown (0) \frown D^{+}.\) 因此，如果 \(A \neq C\) 或 \(B \neq D\) ，则 \(A \frown (0) \frown B^{+} \neq C \frown (0) \frown D^{+}.\)
\(P\) 是由 \(E\) 和函数 \((A,B) \mapsto A \sim (0) \sim B^{+}\) 生成的函数，上述定理断言它是自由生成的（ \(P\) 的一个元素不能用两种不同的方式表示）。由于它是下面证明中的一个重要函数，我们将其缩写为 \(\operatorname{gen} (A,B) :=A \frown (0) \frown B^{+}.\)
定义 2 函数 expand \(: ( P \backslash \{E \} ) \times \mathbb {N} a r r o w \mathbb {N} < \omega\) 定义如下。注意，定义域中的元素 \(S\) 不为空，因此 \(S_{\perp}\) 有定义。
(1) 如果 \(S_{\perp}=0\) ，则 \(\operatorname{expand} (S) :=\operatorname{sub} (S,0,\operatorname{length} (S)-1).\)
(2) 如果 \(S_{\perp} > 0\) ，则（根据引理 1.1.）\(0 \in \{i \in \mathbb {N} \mid i < \operatorname{length} (S) \wedge S_{i} < S_{\square} \},\) 因此 \(\{i \in \mathbb {N} \mid i < \operatorname{length} (S) \wedge S_{i} < S_{\square} \}\) 非空。
定义 \(\operatorname{br} (S) :=\max \{i \in \mathbb {N} \mid i < \operatorname{length} (S) \wedge S_{i} < S_{\square} \},\) \(\operatorname{gp} (S) :=\operatorname{sub} (S,0,\operatorname{br} (S)),\) \(\operatorname{bp} (S) :=\operatorname{sub} (S,\operatorname{br} (S),\operatorname{length} (S)-1),\) \(\operatorname{expand} (S) :=\operatorname{gp} (S) \smile \underbrace {\operatorname{bp} (S) \smile \cdots \smile \operatorname{bp} (S)}_{n}.\)
定理 2 (1) 对于任意 \(A \in P\) ，\(\operatorname{expand} (\operatorname{gen} (A,E),n)=A.\)
(2) 对于任意 \(( A ,B ) \in P^{2}\) ，\(\operatorname{expand} (\operatorname{gen} (A,\operatorname{gen} (B,E)),n)=A \frown \underbrace {(0) \frown B^{+} \frown \cdots \frown (0) \frown B^{+}}_{n}.\)
(3) 对于任意的 \(( A ,B ,C ) \in P^{2} \times ( P \backslash \{E \} )\) ，\(\operatorname{expand} (\operatorname{gen} (A,\operatorname{gen} (B,C)),n)=\operatorname{gen} (A,\operatorname{expand} (\operatorname{gen} (B,C),n)).\)
证明：1. 若 \(S :=\mathrm {gen} ( A ,E )\) ，则 \(S=A \frown (0) \frown E^{+}=A \frown (0).\) 故 \(S_{\perp}=0\) 。因此 \(\operatorname{expand} (S,n)=\operatorname{sub} (S,0,\operatorname{length} (S)-1)=A.\)
2. 若 \(S :=\operatorname{gen} (A,\operatorname{gen} (B,E)),\) 则 \(S=A \frown (0) \frown (B \frown (0) \frown E^{+})^{+}=A \frown (0) \frown B^{+} \frown (1).\) 因此， \(S_{\perp}=1 > 0\)
\(\begin{array}{l} \operatorname{br} (S)=\max \left\{i \in \mathbb {N} \mid i < \operatorname{length} (S) \wedge S_{i} < S_{\square} \right\} \\=\max \left\{i \in \mathbb {N} \mid i < \operatorname{length} (S) \wedge S_{i} < 1 \right\}\\=\max \{i \in \mathbb {N} \mid i < \operatorname{length} (S) \wedge S_{i}=0 \}. \\ \end{array}\)
这里，由于 \(S_{\mathrm {length ~} ( A )}=0\) ，因此 \(\operatorname{length} (A) \in \{i \in \mathbb {N} \mid i < \operatorname{length} (S) \wedge S_{i}=0 \}.\) 另外，对于任意 \(n >\) length \(( S )\) ，\(S_{n}=\left(B^{+} \frown (1)\right)_{n-\text {length} (S)-1}=1 + \left(B \frown (0)\right)_{n-\text {length} (S)-1} > 0\) 所以 \(n \in \{i \in \mathbb {N} \mid i < \operatorname{length} (S) \wedge S_{i}=0 \}.\) 因此，\(\operatorname{br} (S)=\max \left\{i \in \mathbb {N} \mid i < \operatorname{length} (S) \wedge S_{i}=0 \right\}=\operatorname{length} (A).\) 在这种情况下
\(\begin{array}{l} \operatorname{gp} (S)=\operatorname{sub} (S,0,\operatorname{br} (S)) \\=\operatorname{sub} (A \frown (0) \frown B^{+} \frown (1),0 (A))\\=A. \\ \end{array}\)
此外，
\(\begin{array}{l} \operatorname{bp} (S)=\operatorname{sub} (S,\operatorname{br} (S),\operatorname{length} (S)-1) \\=\operatorname{sub} (A \smile (0) \smile B^{+} \smile (1),\text {length} (A),\text {length}. (S)-1) \\=(0) \frown B^{+}. \\ \end{array}\)
因此 \(\operatorname{expand} (S,n)=A \frown \underbrace {(0) \frown B^{+} \frown \cdots \frown (0) \frown B^{+}}_{n}.\)
3. 若 \(S :=\operatorname{gen} (A,\operatorname{gen} (B,C)),\) 则
\(\begin{array}{l} S=A \frown (0) \frown (B \frown (0) \frown C^{+})^{+} \\=A \frown (0) \frown B^{+} \frown (1) \frown C^{+ +}. \\ \end{array}\)
由于 \(C \neq E\) ，\(S_{\square}=C_{\square}^{+ +}=C_{\square} + 2 > 1.\) 又由于 \(S_{\text {length} (A) + 1 + \text {length} (B)}=1,\) \(\operatorname{length} (A) + 1 + \operatorname{length} (B) \in \{i \in \mathbb {N} \mid i < \operatorname{length} (S) \wedge S_{i} < S_{\square} \}.\) 特别地，
\(\begin{array}{l} \operatorname{br} (S)=\max \left\{i \in \mathbb {N} \mid i < \operatorname{length} (S) \wedge S_{i} < S_{\square} \right\}\\ \geq \operatorname{length} (A) + 1 + \operatorname{length} (B). \\ \end{array}\)
令 \(r :=\ker ( S )\) ，则
\(\begin{array}{l} \operatorname{br} (B \frown (0) \frown C^{+}) \\=\max \left\{i \in \mathbb {N} \mid i < \operatorname{length} \left(B \frown (0) \frown C^{+}\right) \right. \\ \land (B \smile (0) \smile C^{+})_{i} < (B \smile (0) \smile C^{+})_{\square} \}. \\ \end{array}\)
由于 \(\operatorname{length} (A) + 1 + \operatorname{length} (B \frown (0) \frown C^{+})=\operatorname{length} (S),\) 我们有 \(S_{\text {length} (A) + 1 + i}=\left(B \frown (0) \frown C^{+}\right)_{i}-1,\) 且 \(S_{\square}=(B \frown (0) \frown C^{+})_{\square}-1,\)
\(\begin{array}{l} \{i \in \mathbb {N} \mid i < \operatorname{length} (B \frown (0) \frown C^{+}) \\ \left. \wedge (B \frown (0) \frown C^{+})_{i} < (B \frown (0) \frown C^{+}) \square \right\} \\=\left\{i \in \mathbb {N} \mid \operatorname{length} (A) + 1 + i < \operatorname{length} (S) \wedge S_{\text {length} (A) + 1 + i}. \right. \\ \end{array}\)
因此
\(\begin{array}{l} \operatorname{br} (B \smile (0) \smile C^{+}) \\=\max \left\{i \in \mathbb {N} \mid i < \text {length} (B \frown (0) \frown C^{+}) \right. \\ \wedge (B \smile (0) \smile C^{+})_{i} < (B \smile (0) \smile C^{+})_{\square} \} \\=r-\operatorname{length} (A)-1. \\ \end{array}\)
因此，\(\operatorname{gp} (B \sim (0) \sim C^{+})=\operatorname{sub} (B \sim (0) \sim C^{+},0,r-\operatorname{length} (A)-1),\) 所以
\(\begin{array}{l} \mathrm {gp} (B \smile (0) \smile C^{+})^{+} \\=\operatorname{sub} \left(\left(B \frown (0) \frown C^{+}\right)^{+},0,r-\text {length}. (A)-1\right) \\=\operatorname{sub} (S \operatorname{length} (A) + 1,r). \\ \end{array}\)
另外，由于
\(\begin{array}{l} \mathrm {bp} (B \frown (0) \frown C^{+})=\operatorname{sub} (B \frown (0) \frown C^{+}, \\ r-\text {length} (A)-1,\text {length} (B \smile (0) \smile C^{+})),\\ \end{array}\)
我们有
\(\begin{array}{l} \mathrm {bp} (B \smile (0) \smile C^{+})^{+} \\=\operatorname{sub} \left(\left(B \frown (0) \frown C^{+}\right)^{+},r-\text {length} (A)-1,\text {length} \left(B \frown (0) \frown C^{+}\right)-1\right) \\=\operatorname{sub} (S,r,\text {length} (S)-1)^{-}. \\ \end{array}\)
此外 \(\operatorname{gp} (S)=\operatorname{sub} (S,0,r),\operatorname{bp} (S)=\operatorname{sub} (S,r,\text {length} (S)-1),\) 因此
\(\begin{array}{l} \operatorname{expand} (B \smile (0) \smile C^{+},n)^{+} \\=\mathrm {gp} (B \frown (0) \frown C^{+})^{+} \frown \\ \underbrace {\operatorname{bp} \left(B \frown (0) \frown C^{+}\right)^{+} \frown \cdots \frown \operatorname{bp} \left(B \frown (0) \frown C^{+}\right)^{+}}_{n} \\=\operatorname{sub} (S,\operatorname{length} (A) + 1,r) \frown \underbrace {\operatorname{bp} (S) \frown \cdots \frown \operatorname{bp} (S)}_{n}. \\ \end{array}\)
于是我们得到
\(\begin{array}{l} \operatorname{expand} (S,n) \\=\operatorname{sub} (S,0,r) \smile \underbrace {\mathrm {bp} (S) \smile \cdots \smile \mathrm {bp} (S)}_{n} \\=A \frown (0) \curvearrowleft \operatorname{sub} (S,\operatorname{length} (A) + 1,r) \curvearrowleft \underbrace {\operatorname{bp} (S) \curvearrowleft \cdots \operatorname{bp}(S)}_{n}\\=A \smile (0) \smile \operatorname{expand} (B \smile (0) \smile C^{+},n)^{+}. \\ \end{array}\)
证毕。
定理 3 对于任意 \(S \in P\) 和 \(n \in \mathbb {N}\) ， \(S=E\) 或 \(\operatorname{expand} ( S ,n ) \in P\) 。
证明：使用结构归纳法构造 \(P\) 。
\(S=E\) 的情况是平凡的。假设存在 \(( T ,U ) \in P^{2}\) 使得 \(S=\mathrm {gen} ( T ,U )\) ，并且两者都满足条件。如果 \(U=E\) ，则根据引理 2.1，展开 \(( S ,n )=T \in P\) 。从这里开始，假设存在 \(( V ,W ) \in P^{2}\) 使得 \(U=\mathrm {gen} ( V ,W )\) ，并且两者都满足条件。如果 \(W=E\) ，则根据引理 2.2 \(S=\operatorname{gen} (T,\operatorname{gen} (V,E)).\) 因此 \(\operatorname{expand} (S,n)=T \frown \underbrace {(0) \frown V^{+} \frown \cdots \frown (0) \frown V^{+}}_{n}.\) 现在，利用数学归纳法，我们可以证明 \(\operatorname{expand} (S,0)=T \in P\) 且 \(\operatorname{expand} (S,k + 1)=\operatorname{expand} (S,k) \frown (0) \frown V^{+}=\operatorname{gen} (\operatorname{expand} (S,k),V)\) 因此对于任何 \(n \in \mathbb {N}\) ，我们可以证明 \(\operatorname{e x pand} ( S ,n ) \in P\) 。如果 \(W \neq E\) ，则 \(S=\operatorname{gen} (T,\operatorname{gen} (V,W)).\) 因此 \(\operatorname{expand} (S,n)=\operatorname{gen} (T,\operatorname{expand} (\operatorname{gen} (V,W),n))=\operatorname{gen} (T,\operatorname{expand} (U,n)) \in P,\) 因此，对于任何 \(S \in P\) ， \(S=E\) 或 \(\operatorname{e x pand} ( S ,n ) \in P\) 。证毕。
引理 2 是根据 \(P\) 的结构对 expand 的行为进行分类的一种方式。引理 3 表明 expand 的输出也是 \(P\) 的一个元素。
通过对 \(P\) 结构进行递归，定义映射 trans: \(P \to \varepsilon_{0}\) ，如下所示。注意， \(\varepsilon_{0}\) 是加法和 \(\omega\) 运算下封闭的序数映射。
定义 3 (1) 如果 \(S=E\) ，则 \(\mathrm {trans} ( S ) :=0\)
(2) 如果存在 \(( A ,B ) \in P^{2}\) 使得 \(S=\mathrm {gen} ( A ,B )\) ，则 \(\operatorname{trans} (S) :=\operatorname{trans} (A) + \omega^ {\operatorname{trans} (B)}.\)
定理 4 对于任意 \(S \in P ,n \in \mathbb {N}\) ，都有 \(S=E\) 或 \(\operatorname{trans} (\operatorname{expand} (S,n)) < \operatorname{trans} (S).\)
证明：通过构造 \(P\) 的结构归纳法来证明。
当 \(S=E\) 时，这是平凡的。从现在开始，假设 \(( T ,U ) \in P^{2}\) 存在，使得 \(S=\mathrm {gen} ( T ,U )\) ，并且两者都满足条件。如果 \(U=E\) ，则 \(S=\mathrm {gen} ( T ,E )\) ，因此根据引理 2.1， \(\operatorname{e x pand} ( S ,n )=T\) 。因此
\(\begin{array}{l} (\operatorname{expand} (S,n)) \\=\operatorname{trans} (T) < \operatorname{trans} (T) + \omega^ {0} \\=\operatorname{trans} (T) + \omega^ {\text {trans}} (E) \\=\operatorname{trans} (\operatorname{gen} (T,E)) \\=\operatorname{trans} (S). \\ \end{array}\)
从现在开始，我们假设 \(( V ,W ) \in P^{2}\) 存在，使得 \(U=\mathrm {gen} ( V ,W )\) 且两者都满足条件。如果 \(W=E\) ，则 \(S=\operatorname{gen} (T,\operatorname{gen} (V,E)),\) 因此
\(\begin{array}{l} \operatorname{trans} (S)) \\=\operatorname{trans} (\operatorname{gen} (T,\operatorname{gen} (V,E)))) \\=\operatorname{trans} (T) + \omega^ {\operatorname{trans} (\mathrm {gen} (V,E))}) \\=\operatorname{trans} (T) + \omega^ {\operatorname{trans} (V) + \omega^ {\operatorname{trans} (E)}} \\=\operatorname{trans} (T) + \omega^ {\operatorname{trans} (V) + 1}. \\ \end{array}\)
另外，根据引理 2.2，\(\operatorname{expand} (S,n)=T \frown \underbrace {(0) \frown V^{+} \frown \cdots \frown (0) \frown V^{+}}_{n}.\) 通过数学归纳法，我们可以证明\(\operatorname{trans} (\operatorname{expand} (S,n))=\operatorname{trans} (T) + \omega^ {\operatorname{trans} (V)} \times n.\) 因此对于任意 \(n \in \mathbb {N}\) ，\(\operatorname{trans} \left(\exp \left(S,n\right)\right)=\operatorname{trans} (T) + \omega^ {\operatorname{trans} (V)} \times n < \operatorname{trans} (T) + \omega^ {\operatorname{trans} (V) + 1}=\operatorname{trans} (S).\) 若 \(W \neq E\) ，则根据引理 2.3 \(\operatorname{expand} (S,n)=\operatorname{gen} (T,\operatorname{expand} (U,n).\) 由于 \(U\) 满足 \(\operatorname{trans} \left(\operatorname{expand} (U,n)\right) < \operatorname{trans} (U)\) 因此
\(\begin{array}{l} \operatorname{trans} (\operatorname{expand} (S,n)) \\=\operatorname{trans} \left(\operatorname{gen} (T,\text {expand} (U,n))\right) \\=\operatorname{trans} (T) + \omega^ {\operatorname{trans} (\exp \left(U,n\right))} \operatorname{trans} (T) + \omega^ {\operatorname{trans} (U)} \\=\operatorname{trans} (S). \\ \end{array}\)
因此，对于任意的 \(S \in P ,n \in \mathbb {N}\) ，都有 \(S=E\) 或 \(\operatorname{trans} ( \exp \mathrm {and} ( S ,n ) ) < \operatorname{trans} ( S )\) 。证毕。
定理 5 对于任意 \(S \in P ,a : \mathbb {N} \mathbb {N}\) ，都存在 \(k \in \mathbb N\) 使得 \(S \left[a_{0} \right]\left[a_{1} \right]\dots \left[a_{k-1} \right]=E.\)
证明：假设这样的 \(k \in \mathbb N\) 不存在。对于每个 \(k \in \mathbb {N}\) ，都有 \(S \left[a_{0} \right]\left[a_{1} \right]\dots \left[a_{k-1} \right]\neq E,\) 因此 \(\operatorname{trans} \left(S[a_{0}][a_{1}]\dots[a_{k-1}]\right) \neq 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 N\) 都有定义。然而，根据引理 4，\(\operatorname{trans} (S) > \operatorname{trans} \left(S \left[a_{0} \right]\right) > \operatorname{trans} \left(S \left[a_{0} \right]\left[a_{1} \right]\right) > \dots\) 这是一个无限递减的序数序列。这与序数的良序性相矛盾。矛盾的是，存在 \(k \in \mathbb N\) 使得 \(S \left[a_{0} \right]\left[a_{1} \right]\dots \left[a_{k-1} \right]=E.\) 这意味着无论选择哪种函数，初等序列都会在有限次数的迭代后都会变成空序列并停止。由此我们证明了 PrSS 的停机性。