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 标准式集是良序的，还要证明它序同构于 ${\epsilon }_0$。

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

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