论文标题
部分组合代数的顺序分析
Ordinal analysis of partial combinatory algebras
论文作者
论文摘要
对于每个部分组合代数（PCA），我们使用序数定义了扩展性关系的层次结构。我们研究了PCA的封闭序列，即这些关系相等的最小列序。我们表明，克莱恩（Kleene）的第一个模型的闭合序列是$ω_1^\ textit {ck} $，而克莱恩（Kleene）第二型模型的闭合序列为$ω_1$。我们计算了Kleene的第一个模型中扩展性关系的确切复杂性，表明它们耗尽了高氧化层次结构。我们还讨论了PCA的嵌入。
For every partial combinatory algebra (pca), we define a hierarchy of extensionality relations using ordinals. We investigate the closure ordinals of pca's, i.e. the smallest ordinals where these relations become equal. We show that the closure ordinal of Kleene's first model is $ω_1^\textit{CK}$ and that the closure ordinal of Kleene's second model is $ω_1$. We calculate the exact complexities of the extensionality relations in Kleene's first model, showing that they exhaust the hyperarithmetical hierarchy. We also discuss embeddings of pca's.
