算术分层

依定义公式中全称量词和存在量词的交替次数及排列次序对算术集(算术谓词)作的分层处理，详细定义为

定义(算术分层)

(1)∑=Ⅱ=｛AN｜A是递归集｝

(2)如果存在n十1(n≥1)元递归谓词R(x，y，……，y)使x∈A当且仅当yyy……QyR(x，y，……，y)则称A为∑集，记作A∈∑(谓词yyy……QyR(x，y，……，y)称为∑谓词)。其中Q为或，依n是偶数还是奇数而定(也就是说A的定义公式是在一个n+1元递归谓词前面加上n个交替出现的存在量词和全称量词，以存在量词开头。)

(3)如果存在n+1(n≥1)元递归谓词R(x，y，…y)使x∈A当且仅当yyy…QyR(x，y，…y)则称A为Ⅱ集，记作A∈Ⅱ(谓词yy∨y…QyR(x，y，…y)称为Ⅱ谓词。)(也就是说A的定义公式是在一个n+1元递归谓词前加交替出现的全称量词和存在量词，以全称量词开头)。

(4)△=Ⅱ∩∑

由于连续若干个存在量词(或连续若干个全称量词)可以应用配对函数合成一个(例如yyR(y，y)zR(l(z)，r(z))，yyR(y，y)zR(l(z)，r(z))(参见配对函数)并且R(y，y)递归当且仅当R(l(z)，r(z))递归)，所以一般文献中只对自然数集分层，而将多元组集与其在配对出数下的象集等同看待。

从定义容易证明算术分层的以下基本性质：

1．A∈∑当且仅当；

2．△=∑=Ⅱ

3．

算术分层的结构可表示如下图：

图 自然数集的算术分层

4．=全体算术集

5．如果B≤A且A∈∑，则B∈∑

如B≤A且A∈Ⅱ，则B∈Ⅱ

6．A∈∑当且仅当对某个B∈Ⅱ，A是B递归可枚举集；

如果A∈∑(或A∈Ⅱ)且对每个B∈∑(B∈Ⅱ)都有B≤A，则称A为∑完全集(Ⅱ完全集)。

例如，∑完全集就是1完全集(比如K=｛x｜φ(x)｝有定义)，Ⅱ完全集就是1完全集的余集(比为K=｛x｜φ(x)无定义｝)。

｛x｜W是有穷集｝是∑完全集｛x｜W是无穷集｝是Ⅱ完全集，｛x是有穷集｝是∑完全集，等等。

应用∑完全集(Ⅱ完全集)的概念，还可得出算术分层的如下一些进一步的性质：

7．对n≥1，φ是完全集(参见跳跃算子)；

8．A∈∑当且仅当A是φ递归可枚举集；

9．A∈△当且仅当A≤φ(从而△=△)；

在有些文献中，为了与解析分层区别，将算术分层中的∑记作，将Ⅱ记作。(参见多一归约，图灵归约，A递归集，A递归可枚举集。)