PrSS VS 康托范式

本条目展示 PrSS 和康托范式的列表分析和互译方法。

枚举

PrSS 表达式	康托范式
$(0)$	$1$
$(0,0)$	$2$
$(0,0,0)$	$3$
$(0,1)=(0,0,0,\cdots )$	$\omega$
$(0,1,0)$	$\omega +1$
$(0,1,0,0)$	$\omega +2$
$(0,1,0,1)=(0,1,0,0,0,\cdots )$	$\omega \times 2$
$(0,1,0,1,0,1)$	$\omega \times 3$
$(0,1,1)=(0,1,0,1,0,1,\cdots )$	${\omega }^2$
$(0,1,1,0)$	${\omega }^2+1$
$(0,1,1,0,1)$	${\omega }^2+\omega$
$(0,1,1,0,1,0)$	${\omega }^2+\omega +1$
$(0,1,1,0,1,0,1)$	${\omega }^2+\omega \times 2$
$(0,1,1,0,1,1)=(0,1,1,0,1,0,1,0,1,\cdots )$	${\omega }^2\times 2$
$(0,1,1,0,1,1,0,1,1)$	${\omega }^2\times 3$
$(0,1,1,1)=(0,1,1,0,1,1,0,1,1,\cdots )$	${\omega }^3$
$(0,1,1,1,1)$	${\omega }^4$
$(0,1,2)=(0,1,1,1,\cdots )$	${\omega }^{\omega }$
$(0,1,2,0,1,2)$	${\omega }^{\omega }\times 2$
$(0,1,2,1)=(0,1,2,0,1,2,0,1,2,\cdots )$	${\omega }^{\omega +1}$
$(0,1,2,1,0,1,2)$	${\omega }^{\omega +1}+{\omega }^{\omega }$
$(0,1,2,1,0,1,2,1)$	${\omega }^{\omega +1}\times 2$
$(0,1,2,1,1)=(0,1,2,1,0,1,2,1,0,1,2,1,\cdots )$	${\omega }^{\omega +2}$
$(0,1,2,1,1,1)$	${\omega }^{\omega +3}$
$(0,1,2,1,2)=(0,1,2,1,1,1,\cdots )$	${\omega }^{\omega \times 2}$
$(0,1,2,1,2,1)$	${\omega }^{\omega \times 2+1}$
$(0,1,2,1,2,1,2)$	${\omega }^{\omega \times 3}$
$(0,1,2,2)=(0,1,2,1,2,1,2,\cdots )$	${\omega }^{{\omega }^2}$
$(0,1,2,2,1)$	${\omega }^{{\omega }^2+1}$
$(0,1,2,2,1,2)$	${\omega }^{{\omega }^2+\omega }$
$(0,1,2,2,1,2,1)$	${\omega }^{{\omega }^2+\omega +1}$
$(0,1,2,2,1,2,1,2)$	${\omega }^{{\omega }^2+\omega \times 2}$
$(0,1,2,2,1,2,2)=(0,1,2,2,1,2,1,2,1,2,\cdots )$	${\omega }^{{\omega }^2*2}$
$(0,1,2,2,2)=(0,1,2,2,1,2,2,1,2,2,\cdots )$	${\omega }^{{\omega }^3}$
$(0,1,2,3)=(0,1,2,2,2,\cdots )$	${\omega }^{{\omega }^{\omega }}$
$(0,1,2,3,2)$	${\omega }^{{\omega }^{\omega +1}}$
$(0,1,2,3,2,3)$	${\omega }^{{\omega }^{\omega \times 2}}$
$(0,1,2,3,3)$	${\omega }^{{\omega }^{{\omega }^2}}$
$(0,1,2,3,4)=(0,1,2,3,3,3,\cdots )$	${\omega }^{{\omega }^{{\omega }^{\omega }}}$
$(0,1,2,3,4,5,...)=\mathrm{L}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{t}\mathrm{o}\mathrm{f}\mathrm{P}\mathrm{r}\mathrm{S}\mathrm{S}$	${\epsilon }_0$

最终得到，PrSS 的极限是 ${\epsilon }_0$.

互译方法

PrSS 和康托范式之间存在直接的转换关系．下面介绍 PrSS 到康托范式的转换：

对于待转换的 PrSS 表达式 $S$，首先找到 $S$ 中所有的项 $0$，以这些 $0$ 为起点把 $S$ 分为若干个以 $0$ 开头的子表达式，并在中间用加号连接．如果一个子表达式只有一项，即 $(0)$，则将其变为 $1$．否则，将 $(0,X)$ 变换为 ${\omega }^{X^{\prime }}$，其中 $X^{\prime }$ 是将 $X$ 中所有的项都减一后得到的表达式．

然后继续对 $X^{\prime }$ 递归地进行操作，直到无法操作为止，就得到了对应的康托范式．

例如 PrSS 表达式 $(0,1,2,2,0,1,2,1,1,0,1,2,1,1,0,1,1,1)$，首先把它分为若干个 $0$ 开头的子表达式并用加号连接，得到 $(0,1,2,2)+(0,1,2,1,1)+(0,1,2,1,1)+(0,1,1,1)$，随后将每个子表达式按照 $(0,X)\mapsto {\omega }^{X^{\prime }}$ 的形式变换，得到 ${\omega }^{(0,1,1)}+{\omega }^{(0,1,0,0)}+{\omega }^{(0,1,0,0)}+{\omega }^{(0,0,0)}$．随后，把指数上的 PrSS 继续递归变换．$(0,1,1)$ 变换为 ${\omega }^{(0,0)}={\omega }^{1+1}={\omega }^2$．$(0,1,0,0)$ 变换为 ${\omega }^1+1+1=\omega +2$．而 $(0,0,0)$ 就是 $1+1+1=3$．因此我们便得到了 $(0,1,2,2,0,1,2,1,1,0,1,2,1,1,0,1,1,1)$ 对应的康托范式 ${\omega }^{{\omega }^2}+{\omega }^{\omega +2}\times 2+{\omega }^3$．

证明

设 $S$ 是一个 PrSS 表达式，我们用 $T(S)$ 表示 $S$ 所对应的序数。例如，若 $S=(0,1,2)$，则 $T(S)={\omega }^{\omega }$。

设 $S_1,S_2$ 是两个 PrSS 表达式，我们用 $(S_1,S_2)$ 表示将 $S_1,S_2$ 首尾相连得到的 PrSS 表达式。例如，若 $S_1=(0,1,2)$，$S_2=(0,1)$，则 $(S_1,S_2)=(0,1,2,0,1)$。

设 $S$ 是一个 PrSS 表达式，我们用 $(0,S+1)$ 表示首项为 $0$，其余项为 $S$ 中每一项 $+1$ 得到的自然数列。例如，若 $S=(0,1,2,0,1)$，则 $(0,S+1)=(0,1,2,3,1,2)$。

设 $S$ 是一个 PrSS 表达式，我们用 $(S,1)$ 表示首项为在 $S$ 结尾添加一项 $1$ 得到的自然数列。例如，若 $S=(0,1,2,1)$，则 $(S,1)=(0,1,2,1,1)$。

下面我们证明 PrSS 表达式与康托范式的互译方法。证明过程分为三步：

1. 设 $S_1,S_2$ 是两个 PrSS 表达式，则 $T((S_1,S_2))=T(S_1)+T(S_2)$。
2. 设 $S$ 是一个 PrSS 表达式，且除首项为 $0$ 外不含其他 $0$ 项，则 $T((S,1))=T(S)\cdot \omega$。
3. 设 $S$ 是一个 PrSS 表达式，则 $T((0,S+1))={\omega }^{T(S)}$。

命题 1：设 $S_1,S_2$ 是两个 PrSS 表达式，则 $T((S_1,S_2))=T(S_1)+T(S_2)$。

对 $S_2$ 使用超限归纳法。

若 $S_2$ 是空表达式，则 $T(S_2)=0$ 且 $(S_1,S_2)=S_1$。所以 $T((S_1,S_2))=T(S_1)+T(S_2)$ 成立。

若 $S_2$ 是后继表达式，设 $S_2=(S_3,0)$，则 $T(S_2)=T(S_3)+1$。
根据归纳假设，有 $T((S_1,S_3))=T(S_1)+T(S_3)$。
所以 $T((S_1,S_2))=T((S_1,S_3,0))=T((S_1,S_3))+1=(T(S_1)+T(S_3))+1=T(S_1)+(T(S_3)+1)=T(S_1)+T(S_2)$。

若 $S_2$ 是极限表达式，设 $S_2$ 的展开式为 $R_0,R_1,R_2,\cdots$。
从坏根的定义可以看出，$(S_1,S_2)$ 的坏根位于 $S_2$ 部分，所以 $(S_1,S_2)$ 的坏部包含于 $S_2$ 部分，所以 $(S_1,S_2)$ 的展开式为 $(S_1,R_0),(S_1,R_1),(S_1,R_2),\cdots$。
根据归纳假设，$T(S_1,R_n)=T(S_1)+T(R_n),\mathrm{\forall }n\in \mathbb{\mathbb{N}}$。
所以 $T((S_1,S_2))=\sup \{T(S_1,R_0),T(S_1,R_1),T(S_1,R_2),\cdots \}=\sup \{T(S_1)+T(R_0),T(S_1)+T(R_1),T(S_2)+T(R_2),\cdots \}=T(S_1)+\sup \{T(R_0),T(R_1),T(R_2),\cdots \}=T(S_1)+T(S_2)$。

由超限归纳法我们得出，对任意 PrSS 表达式 $S_2$，有 $T((S_1,S_2))=T(S_1)+T(S_2)$。

命题 2：设 $S$ 是一个 PrSS 表达式，且除首项为 $0$ 外不含其他 $0$ 项，则 $T((S,1))=T(S)\cdot \omega$。

从坏根的定义可以看出，$(S,1)$ 的坏根是首项 $0$，所以 $(S,1)$ 的展开式为 $(),S,(S,S),\cdots$，其中第 $n$ 项为 $n$ 个 $S$ 首尾相连。
根据命题 1，这个基本列的第 $n$ 项为 $T(S)\cdot n$。所以 $T((S,1))=\sup \{T(S)\cdot 0,T(S)\cdot 1,T(S),\cdot 2\}=T(S)\cdot \omega$。

命题 3：设 $S$ 是一个 PrSS 表达式，则 $T((0,S+1))={\omega }^{T(S)}$。

对 $S$ 使用超限归纳法。

若 $S$ 是空表达式，则 $T(S)=0$ 且 $(0,S+1)=(0)$。所以 $T((0,S+1))=1={\omega }^0={\omega }^{T(S)}$ 成立。

若 $S$ 是后继表达式，设 $S=(S^{\prime },0)$，则 $T(S)=T(S^{\prime })+1$。
根据归纳假设，有 $T((0,S^{\prime }+1))={\omega }^{T(S^{\prime })}$。
因为 $(0,S^{\prime }+1)$ 除首项为 $0$ 外不含其他 $0$ 项，根据命题 2，有 $T((0,S^{\prime }+1,1))=T((0,S^{\prime }+1))\cdot \omega$。
所以 $T((0,S+1))=T((0,S^{\prime }+1,1))=T((0,S^{\prime }+1))\cdot \omega ={\omega }^{T(S^{\prime })}\cdot \omega ={\omega }^{T(S^{\prime })+1}={\omega }^{T(S)}$。

若 $S$ 是极限表达式，设 $S$ 的展开式为 $S_0,S_1,S_2,\cdots$。
从坏根的定义可以看出，$(0,S+1)$ 的坏根位于 $S+1$ 部分，所以 $(0,S+1)$ 的坏部包含于 $S+1$ 部分，所以 $(0,S+1)$ 的展开式为 $(0,S_0+1),(0,S_1+1),(0,S_2+1)\cdots$。
根据归纳假设，$T(0,S_n+1)={\omega }^{T(S_n)},\mathrm{\forall }n\in \mathbb{\mathbb{N}}$。
所以 $T((0,S+1))=\sup \{T(0,S_0+1),T(0,S_1+1),T(0,S_2+1),\cdots \}=\sup \{{\omega }^{T(S_0)},{\omega }^{T(S_1)},{\omega }^{T(S_2)},\cdots \}={\omega }^{\sup \{T(S_0),T(S_1),T(S_2),\cdots \}}={\omega }^{T(S)}$。

由超限归纳法我们得出，对任意 PrSS 表达式 $S$，有 $T((0,S+1))={\omega }^{T(S)}$。