查看“︁PrSS 的良序性”︁的源代码

== PrSS 没有无穷降链 ==

首先我们将 [[初等序列系统|PrSS]] 的每个合法表达式 <math>S</math> 对应于一个不超过 <math>\varepsilon_0</math> 的[[序数]] <math>F(S)</math>。然后我们证明 PrSS 表达式展开时，其对应的序数严格递减。于是就可以依据 <math>\varepsilon_0</math> 的[[良序|良序性]]说明 PrSS 没有无穷降链。

'''第一步'''：将 PrSS 的每个合法表达式对应于一个不超过 <math>\varepsilon_0</math> 的序数。

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

任取 PrSS 合法表达式 <math>S=(a_1,a_2,\cdots,a_n)</math>。

若 <math>n=0</math>，则 <math>F(S)=0<\varepsilon_0</math>。

若 <math>n>0</math>，分两种情况讨论：

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

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

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

任取 PrSS 表达式 <math>S=(a_1,a_2,\cdots,a_n)</math>。

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

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

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

若 <math>a_n\neq 0</math>，分为三种情况讨论：

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

证毕。

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

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

== PrSS 标准表达式 ==

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

'''定义'''（PrSS 标准表达式）

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

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

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

'''定义'''（字典序）

设 <math>A</math> 是一个全序集，其上的全序是 <math>\le</math>。考虑两个数列 <math>S=(a_1,a_2,\cdots,a_n)</math> 和 <math>T=(b_1,b_2,\cdots,b_m)</math>，其中 <math>a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_m\in A</math>。在字典序下，<math>S\le T</math> 当且仅当以下两条中的一条成立：
* 存在 <math>0\le k<\min\{n,m\}</math> 使得对任意 <math>i\in\{1,2,\cdots,k\}</math> 有 <math>a_i=b_i</math>，但 <math>a_{k+1}<b_{k+1}</math>；
* 对任意 <math>i\in\{1,2,\cdots,\min\{n,m\}\}</math> 有 <math>a_i=b_i</math>，且 <math>n\le m</math>。

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

'''引理'''

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

'''证明'''

设 <math>S=(a_1,a_2,\cdots,a_n)</math> 是 PrSS 表达式。

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

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

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

证毕。

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

'''临时定义'''（PrSS 规范式）

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

若 <math>n=0</math>，则 <math>S=()</math> 是 PrSS 规范式。

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

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

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

'''定理'''

PrSS 标准式都是 PrSS 规范式。

'''证明'''

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

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

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

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

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

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

证毕。

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

== PrSS 标准式集的良序性 ==

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

'''定理'''

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

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

'''证明'''

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

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

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

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

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

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

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

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

证毕。

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

'''定理'''

PrSS 规范式都是 PrSS 标准式。

'''证明'''

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

证毕。

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

但我们不止于此。下一节，我们要证明 PrSS 标准式集[[良序|序同构]]于 <math>\varepsilon_0</math>。

== PrSS 标准式集的序型 ==

为了证明 PrSS 标准式集[[良序|序同构]]于 <math>\varepsilon_0</math>，我们要证明第一节定义的保序映射 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的双射，结合 PrSS 标准式集的全序性，就能说明 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的序同构。

【未完】

[[分类:证明]]