图灵度

简称T度，自然数集在≡关系下的等价类称为图灵度，含有自然数集A的图灵度记作d(A)：

d(A)=｛B｜B≡A｝

含有递归可枚举集的T度称为递归可枚举的T度。

如果A≤B，则称d(A)≤d(B)

常用a、b等符号表示图灵度。

全体递归集组成一个图灵度，记作o；全体T完全集组成一个图灵度，记作o′；

任给AN，如果a=d(A)，则记a′=d(A′)(参看跳跃算子)。

图灵度有以下一些基本性质：

(1)a≤a′且 a≠a′；

(2)如果a≤b 则a′≤b′；

(3)o≤a

(4)o′≤a′

(5)如果A∈a、B∈b且B是A递归可枚举集，则b≤a′。

(6)任给T度a、b，a、b有最小上界(记作a∪b)

(7)每个非递归的递归可枚举T度都含有单纯集。

全体图灵度构成了一个上半格，可以用以下图形表示：

图 图灵度

图灵度的结构是近三十余年递归论研究的一个重要方面，比较重要的结果有：

定理1(Friedberg-Mnchnic) 存在两个递归可枚举的图灵度a、b使ab且ba，因而o＜a＜o′(o＜a意义为o≤a且o≠a)(参见波斯特问题)。

定理2 对任何递归可枚举的T度a，如果o＜a＜o′，则存在递归可枚举的T度b使a、b不可比较(即ab且ba)。

定理3(Sacks稠密性定理) 任给递归可枚举的T度a、b，如果a＜b，则存在递归可枚举的T度c使a＜c＜b。

定理4(Sacks分岔定理) 任给递归可枚举的T度a，如果o＜a，则存在递归可枚举的T度b和c，使得b＜a，c＜a而b和c不可比较。

定理5(Shoenfield) 存在非递归可枚举的T度a使a＜To′。

定理6(Lachlan，Yates)

　(1)存在递归可枚举的T度b、c使得o＜b，o＜c，并且o是b、c的最大下界。

　(2)存在递归可枚举的T度a、b，它们没有最大下界。

定理7(极小度)，存在T度m，使m≠o，且不存在T度a满足o＜a＜m(度m称为极小度，由定理3知m不是递归可枚举的T度)。