查看“︁PrSS VS 康托范式”︁的源代码

本条目展示 [[初等序列系统|PrSS]] 和[[康托范式]]的列表分析和互译方法。

== 枚举 ==
{| class="wikitable"
|-
! PrSS 表达式 !! 康托范式
|-
| <math>(0)</math> || <math>1</math>
|-
| <math>(0,0)</math> || <math>2</math>
|-
| <math>(0,0,0)</math> || <math>3</math>
|-
| <math>(0,1)=({\color{red}0},{\color{green}0},{\color{blue}0},\cdots)</math> || <math>\omega</math>
|-
| <math>(0,1,0)</math> || <math>\omega+1</math>
|-
| <math>(0,1,0,0)</math> || <math>\omega+2</math>
|-
| <math>(0,1,0,1)=(0,1,{\color{red}0},{\color{green}0},{\color{blue}0},\cdots)</math> || <math>\omega\times 2</math>
|-
| <math>(0,1,0,1,0,1)</math> || <math>\omega\times 3</math>
|-
| <math>(0,1,1)=({\color{red}0,1},{\color{green}0,1},{\color{blue}0,1},\cdots)</math> || <math>\omega^{2}</math>
|-
| <math>(0,1,1,0)</math> || <math>\omega^{2}+1</math>
|-
| <math>(0,1,1,0,1)</math> || <math>\omega^{2}+\omega</math>
|-
| <math>(0,1,1,0,1,0)</math> || <math>\omega^{2}+\omega+1</math>
|-
| <math>(0,1,1,0,1,0,1)</math> || <math>\omega^{2}+\omega\times 2</math>
|-
| <math>(0,1,1,0,1,1)=(0,1,1,{\color{red}0,1},{\color{green}0,1},{\color{blue}0,1},\cdots)</math> || <math>\omega^{2}\times 2</math>
|-
| <math>(0,1,1,0,1,1,0,1,1)</math> || <math>\omega^{2}\times 3</math>
|-
| <math>(0,1,1,1)=({\color{red}0,1,1},{\color{green}0,1,1},{\color{blue}0,1,1},\cdots)</math> || <math>\omega^{3}</math>
|-
| <math>(0,1,1,1,1)</math> || <math>\omega^{4}</math>
|-
| <math>(0,1,2)=(0,{\color{red}1},{\color{green}1},{\color{blue}1},\cdots)</math> || <math>\omega^{\omega}</math>
|-
| <math>(0,1,2,0,1,2)</math> || <math>\omega^{\omega}\times 2</math>
|-
| <math>(0,1,2,1)=({\color{red}0,1,2},{\color{green}0,1,2},{\color{blue}0,1,2},\cdots)</math> || <math>\omega^{\omega+1}</math>
|-
| <math>(0,1,2,1,0,1,2)</math> || <math>\omega^{\omega+1}+\omega^{\omega}</math>
|-
| <math>(0,1,2,1,0,1,2,1)</math> || <math>\omega^{\omega+1}\times 2</math>
|-
| <math>(0,1,2,1,1)=({\color{red}0,1,2,1},{\color{green}0,1,2,1},{\color{blue}0,1,2,1},\cdots)</math> || <math>\omega^{\omega+2}</math>
|-
| <math>(0,1,2,1,1,1)</math> || <math>\omega^{\omega+3}</math>
|-
| <math>(0,1,2,1,2)=(0,1,2,{\color{red}1},{\color{green}1},{\color{blue}1},\cdots)</math> || <math>\omega^{\omega\times 2}</math>
|-
| <math>(0,1,2,1,2,1)</math> || <math>\omega^{\omega\times 2+1}</math>
|-
| <math>(0,1,2,1,2,1,2)</math> || <math>\omega^{\omega\times 3}</math>
|-
| <math>(0,1,2,2)=(0,{\color{red}1,2},{\color{green}1,2},{\color{blue}1,2},\cdots)</math> || <math>\omega^{\omega^{2}}</math>
|-
| <math>(0,1,2,2,1)</math> || <math>\omega^{\omega^{2}+1}</math>
|-
| <math>(0,1,2,2,1,2)</math> || <math>\omega^{\omega^{2}+\omega}</math>
|-
| <math>(0,1,2,2,1,2,1)</math> || <math>\omega^{\omega^{2}+\omega+1}</math>
|-
| <math>(0,1,2,2,1,2,1,2)</math> || <math>\omega^{\omega^{2}+\omega\times 2}</math>
|-
| <math>(0,1,2,2,1,2,2)=(0,1,2,2,{\color{red}1,2},{\color{green}1,2},{\color{blue}1,2},\cdots)</math> || <math>\omega^{\omega^{2}*2}</math>
|-
| <math>(0,1,2,2,2)=(0,{\color{red}1,2,2},{\color{green}1,2,2},{\color{blue}1,2,2},\cdots)</math> || <math>\omega^{\omega^{3}}</math>
|-
| <math>(0,1,2,3)=(0,1,{\color{red}2},{\color{green}2},{\color{blue}2},\cdots)</math> || <math>\omega^{\omega^{\omega}}</math>
|-
| <math>(0,1,2,3,2)</math> || <math>\omega^{\omega^{\omega+1}}</math>
|-
| <math>(0,1,2,3,2,3)</math> || <math>\omega^{\omega^{\omega\times 2}}</math>
|-
| <math>(0,1,2,3,3)</math> || <math>\omega^{\omega^{\omega^{2}}}</math>
|-
| <math>(0,1,2,3,4)=(0,1,2,{\color{red}3},{\color{green}3},{\color{blue}3},\cdots)</math> || <math>\omega^{\omega^{\omega^{\omega}}}</math>
|-
| <math>(0,1,2,3,4,5,...)=\mathrm{Limit\ of\ PrSS} </math> || <math>\varepsilon_{0}</math> 
|}

最终得到，PrSS 的极限是 <math>\varepsilon_0</math>.

== 互译方法 ==
PrSS 和[[康托范式]]之间存在直接的转换关系．下面介绍 PrSS 到康托范式的转换：

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

然后继续对 <math>X'</math> 递归地进行操作，直到无法操作为止，就得到了对应的康托范式．

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

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

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

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

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

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

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

 命题 1：设 <math>S_1,S_2</math> 是两个 PrSS 表达式，则 <math>T((S_1,S_2))=T(S_1)+T(S_2)</math>。
 
 对 <math>S_2</math> 使用超限归纳法。
 
 若 <math>S_2</math> 是空表达式，则 <math>T(S_2)=0</math> 且 <math>(S_1,S_2)=S_1</math>。所以 <math>T((S_1,S_2))=T(S_1)+T(S_2)</math> 成立。
 
 若 <math>S_2</math> 是后继表达式，设 <math>S_2=(S_3,0)</math>，则 <math>T(S_2)=T(S_3)+1</math>。
 根据归纳假设，有 <math>T((S_1,S_3))=T(S_1)+T(S_3)</math>。
 所以 <math>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)</math>。
 
 若 <math>S_2</math> 是极限表达式，设 <math>S_2</math> 的展开式为 <math>R_0,R_1,R_2,\cdots</math>。
 从坏根的定义可以看出，<math>(S_1,S_2)</math> 的坏根位于 <math>S_2</math> 部分，所以 <math>(S_1,S_2)</math> 的坏部包含于 <math>S_2</math> 部分，所以 <math>(S_1,S_2)</math> 的展开式为 <math>(S_1,R_0),(S_1,R_1),(S_1,R_2),\cdots</math>。
 根据归纳假设，<math>T(S_1,R_n)=T(S_1)+T(R_n),\quad\forall n\in\N</math>。
 所以 <math>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)</math>。
 
 由超限归纳法我们得出，对任意 PrSS 表达式 <math>S_2</math>，有 <math>T((S_1,S_2))=T(S_1)+T(S_2)</math>。

 命题 2：设 <math>S</math> 是一个 PrSS 表达式，且除首项为 <math>0</math> 外不含其他 <math>0</math> 项，则 <math>T((S,1))=T(S)\cdot\omega</math>。
 
 从坏根的定义可以看出，<math>(S,1)</math> 的坏根是首项 <math>0</math>，所以 <math>(S,1)</math> 的展开式为 <math>(),S,(S,S),\cdots</math>，其中第 <math>n</math> 项为 <math>n</math> 个 <math>S</math> 首尾相连。
 根据命题 1，这个基本列的第 <math>n</math> 项为 <math>T(S)\cdot n</math>。所以 <math>T((S,1))=\sup\{T(S)\cdot 0,T(S)\cdot 1,T(S),\cdot 2\}=T(S)\cdot\omega</math>。

 命题 3：设 <math>S</math> 是一个 PrSS 表达式，则 <math>T((0,S+1))=\omega^{T(S)}</math>。
 
 对 <math>S</math> 使用超限归纳法。
 
 若 <math>S</math> 是空表达式，则 <math>T(S)=0</math> 且 <math>(0,S+1)=(0)</math>。所以 <math>T((0,S+1))=1=\omega^0=\omega^{T(S)}</math> 成立。
 
 若 <math>S</math> 是后继表达式，设 <math>S=(S',0)</math>，则 <math>T(S)=T(S')+1</math>。
 根据归纳假设，有 <math>T((0,S'+1))=\omega^{T(S')}</math>。
 因为 <math>(0,S'+1)</math> 除首项为 <math>0</math> 外不含其他 <math>0</math> 项，根据命题 2，有 <math>T((0,S'+1,1))=T((0,S'+1))\cdot\omega</math>。
 所以 <math>T((0,S+1))=T((0,S'+1,1))=T((0,S'+1))\cdot\omega=\omega^{T(S')}\cdot\omega=\omega^{T(S')+1}=\omega^{T(S)}</math>。
 
 若 <math>S</math> 是极限表达式，设 <math>S</math> 的展开式为 <math>S_0,S_1,S_2,\cdots</math>。
 从坏根的定义可以看出，<math>(0,S+1)</math> 的坏根位于 <math>S+1</math> 部分，所以 <math>(0,S+1)</math> 的坏部包含于 <math>S+1</math> 部分，所以 <math>(0,S+1)</math> 的展开式为 <math>(0,S_0+1),(0,S_1+1),(0,S_2+1)\cdots</math>。
 根据归纳假设，<math>T(0,S_n+1)=\omega^{T(S_n)},\quad\forall n\in\N</math>。
 所以 <math>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)}</math>。
 
 由超限归纳法我们得出，对任意 PrSS 表达式 <math>S</math>，有 <math>T((0,S+1))=\omega^{T(S)}</math>。

[[分类:分析]]