第406章 44.算术阶层与图灵

在算术体系中,除了我们熟悉的四则运算、高德纳箭头、康威链外,还有一种名为“量词”的存在。

量词分为存在量词?和全称量词?。

(定义计算器或计数器:φ(0)=?,φ(1)=?,……)

数学家克林给“命题”进行了一次分级:

没有量词的命题是零阶命题,而有量词的命题开头必然是存在量词和全称量词交错组成,交错的次数为n,就是n阶名词。

如果一个n阶命题的开头是存在量词,就叫做n阶存在命题,开头是n阶全称量词,就叫做n阶全称命题。

克林将0阶命题定义的自然数集组成的集合写作Δ0,n阶存在命题和n阶全称命题定义的自然数集组成的集合分别写作∑_n和‖_n。

n阶命题完全等价于n阶算术阶层。

(根据我询问的一位大佬指出:算术阶层是将自然数子集按定义它们的命题的复杂性来分层,这里谈不上算术阶层等价算术命题,而是一类算术命题定义了一个阶层的集合。)

这些集合组成了一个无限向上绵延的体系,阶级越高则能够定义的自然数集合越多,表达能力越强。

每一层级都只能被自身和更上层级所定义,层级之间的关系是严格包含+绝对凌驾的。

0阶命题Δ0所代表的是递归函数,是可计算的(参考四则运算、高德纳箭头、超运算)。

∑_1是枚举函数,它初步定义的函数仍然是可计算的(参考tree函数、scg函数等),深入定义后的函数则是不可计算的,例如停机问题。(停机集的图灵度则是由Δ2集合构成)

后续还有∑_2、∑_3、……无止境向上绵延。

算术阶层是无限向上绵延的,图灵度同样如此。