チューリング次数
チューリング次数は関係 ≡ T {\displaystyle \equiv _{T}} の同値類である。 [ X ] {\displaystyle [X]} と書いて集合 X {\displaystyle X} を含むような同値類を表す。 チューリング次数全体を表す記号として D {\displaystyle {\mathcal {D}}} と書く。
チューリング次数は半順序 ≤ {\displaystyle \leq } を持つ。定義として、 [ X ] ≤ [ Y ] {\displaystyle [X]\leq [Y]} である必要十分条件は X ≤ T Y {\displaystyle X\leq _{T}Y} である。計算可能集合を全て含む特別なチューリング次数が存在し、この次数は他の如何なる次数よりも小さい。この次数は半順序集合 D {\displaystyle {\mathcal {D}}} の最小元なので、0(ゼロ)と書く。(チューリング次数を表記する際は、集合と混同しないように太字 (boldface) で書くのが普通である。混同する恐れが無いなら(例えば [ X ] {\displaystyle [X]} )太字にせずとも良い。)
任意の集合 X {\displaystyle X} と Y {\displaystyle Y} について、 X {\displaystyle X} と Y {\displaystyle Y} の結び( X ⊕ Y {\displaystyle X\oplus Y} と書く)を、集合 2 n : n ∈ X {\displaystyle {2n:n\in X}} と 2 m + 1 : m ∈ Y {\displaystyle {2m+1:m\in Y}} の和集合として定義できる。