查看“︁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 标准式集是良序的，还要证明它[[良序|序同构]]于 <math>\varepsilon_0</math>。

为此，我们首先证明上一节所述字典序是全序，结合第一节所证 PrSS 没有无穷降链，就能说明 PrSS 标准式集是良序的。

接下来，我们证明第一节定义的保序映射 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的双射，结合 PrSS 标准式集的全序性，就能说明 <math>F</math> 是 PrSS 标准式集和 <math>\varepsilon_0</math> 之间的序同构。

[[分类:证明]]