チューリング次数
全ての次数 a について、a と a′の厳密に中間に位置する次数が存在する。実際に、a と a′の間にある互いに比較不可能な次数の対は可算個存在する。
ある次数 a が b′と書ける必要十分条件は、0′≤ a。
如何なる次数 a についても、次数 b が存在して、a < b かつ b′= a′を満たす。このような次数 b を a から相対的に「低い」と呼ぶ。
全ての i について、 a i + 1 ′ ≤ a i {\displaystyle \mathbf {a} '_{i+1}\leq \mathbf {a} _{i}} を満たすような次数の無限列 ai が存在する。
帰納的可算集合を持つ次数は r.e.(recursively enumerable 帰納的可算)または c.e.(computably enumerable 計算可枚挙) と呼ばれる。全ての r.e.次数は 0′よりも小さいか等しい。しかしながら 0′よりも小さい全ての次数が r.e.次数という訳ではない。
(G. E. Sacks, 1964) r.e.次数は稠密。任意の二つのr.e.次数の間には、必ず別のr.e.次数がある。
(A. H. Lachlan, 1966a and C. E. M. Yates, 1966) r.e.次数の中には下限を持たないような、r.e.次数の対が存在する。
(A. H. Lachlan, 1966a and C. E. M. Yates, 1966) 下限が 0 であるような 0 でないr.e.次数の対が一つ存在する。
(S. K. Thomason, 1971) 全ての有限な分配束はr.