チューリング次数
この記事では以後「集合」と言えば「自然数の集合」を指すこととする。ある数が集合 X {\displaystyle X} の元かどうかを、オラクル集合 Y {\displaystyle Y} を持つ神託機械を用いて決定できるとき、 X {\displaystyle X} は Y {\displaystyle Y} にチューリング還元可能であると言い、 X ≤ T Y {\displaystyle X\leq _{T}Y} と書く。
二つの集合 X {\displaystyle X} と Y {\displaystyle Y} について、 X {\displaystyle X} が Y {\displaystyle Y} にチューリング還元可能であり、かつ、 Y {\displaystyle Y} が X {\displaystyle X} にチューリング還元可能であるとき、これらの集合は チューリング同値 であると言い、 X ≡ T Y {\displaystyle X\equiv _{T}Y} と書く。
(Simpson, 1977) D {\displaystyle {\mathcal {D}}} の言語{ ⟨ ≤ , = ⟩ {\displaystyle \left\langle \leq ,=\right\rangle } } または { ⟨ ≤ , ′ , = ⟩ {\displaystyle \left\langle \leq ,',=\right\rangle } } を用いた一階理論は真の二階算術に多対一同値。これは D {\displaystyle {\mathcal {D}}} の構造が極端に複雑であることを示している。
(Shore and Slaman, 1999) ジャンプ作用素は次数の一階構造の中で言語 ⟨ ≤ , = ⟩ {\displaystyle \left\langle \leq ,=\right\rangle } を用いて定義可能。
≡ T {\displaystyle \equiv _{T}} という関係は同値関係と捉えることができる。すなわち任意の集合 X {\displaystyle X} 、 Y {\displaystyle Y} 、 Z {\displaystyle Z} について
X ≡ T X {\displaystyle X\equiv _{T}X}
X ≡ T Y {\displaystyle X\equiv _{T}Y} ならば Y ≡ T X {\displaystyle Y\equiv _{T}X}
もし X ≡ T Y {\displaystyle X\equiv _{T}Y} かつ Y ≡ T Z {\displaystyle Y\equiv _{T}Z} ならば、 X ≡ T Z {\displaystyle X\equiv _{T}Z} 。
これらの要件は「優先順序」(要件と自然数との間の明示的な全単射)に従って並べられる。 証明は個々の自然数毎に一つずつの「段階」を踏んで帰納法的に進む。ここでいう段階とは、 X {\displaystyle X} の内容を枚挙する過程だと思えばよい。 個々の段階では、何らかの数を X {\displaystyle X} に加えるか、又は X {\displaystyle X} に加えることを恒久的に禁止して、「要件」を満足させていく(つまり X {\displaystyle X} の全てが枚挙されたなら全ての要件が成り立つように強いる)。 時として、ある数を X {\displaystyle X} に加えると、一つの要件が満たされる代わりにそれまで満たされていた別の要件が満たされなくなる(「傷付けられる」と言う)ことが起きる。 この場合は要件の優先順序を用いてどの要件を満たすべきかを決定する。 大まかなアイディアとしては、もし何らかの要件が傷付けられるなら、それより優先度が高い他の要件が何れ全て傷付けられなくなれば、最終的には傷付けられなくなるだろう、ということである。とはいえ全ての優先度論法がこのような性質を持つ訳ではない。 出来上がった集合 X {\displaystyle X} が r.e.であり全ての要件を満たすことを論証する必要がある。 優先度論法は r.e.集合に関する様々な証明に使える。所期の集合を生成するには、要件とその満たし方を注意深く選ばねばならない。