帰納的可算集合
この集合は、チューリングマシンが停止する入力パラメータ群を表すことで、チューリングマシンの停止問題の符号化となる。
ある計算可能関数にゲーデル数 φ {\displaystyle \phi } が与えられたとき、集合 { ⟨ x , y , z ⟩ ∣ φ x ( y ) = z } {\displaystyle \lbrace \left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\rbrace } は帰納的可算である。この集合は関数値を決定する問題の符号化である。
自然数から自然数への部分関数 f があるとき、f が部分再帰関数である必要十分条件は、f(x) が定義されるような全ての対 ⟨ x , f ( x ) ⟩ {\displaystyle \langle x,f(x)\rangle } の集合が帰納的可算であることである。
A と B が共に帰納的可算集合なら、A ∩ B 、 A ∪ B 、 A × B も帰納的可算集合である。部分再帰関数における帰納的可算集合の逆像は帰納的可算集合である。
ある集合が帰納的可算である必要十分条件は、それが算術的階層のレベル Σ 1 0 {\displaystyle \Sigma _{1}^{0}} にあることである。
集合 T {\displaystyle T} の補集合 N ∖ T {\displaystyle \mathbb {N} \setminus T} が帰納的可算である場合、 T {\displaystyle T} は co-r.e. と呼ばれる。同様に、ある集合が co-r.e. である必要十分条件は、それが算術的階層のレベル Π 1 0 {\displaystyle \Pi _{1}^{0}} にあることである。
集合 A が帰納的(計算可能)である必要十分条件は、A と A の補集合が共に帰納的可算集合であることである。これは帰納的可算集合の束に於いて帰納的関数のクラスが定義可能であることを示す。(すなわち補元を持つ元が帰納的可算集合である。)ある集合が帰納的である必要十分条件は、その集合が何らかの単調増加な全域再帰関数の値域になっているか、または有限なことである。
互いに素な帰納的可算集合同士の対を取ると、あるものは帰納的分離可能であり、あるものは帰納的分離不可能である。対照的に、任意の互いに素な co-r.e. 集合対が帰納的分離可能であることが、次の性質から示される。
集合 S は帰納的可算である。すなわち、S はある部分再帰関数の定義域である。 次のような部分再帰関数 f が存在する: f ( x ) = { 0 if x ∈ S undefined/does not halt if x ∉ S {\displaystyle f(x)=\left\{{\begin{matrix}0&{\mbox{if}}\ x\in S\\{\mbox{undefined/does not halt}}\ &{\mbox{if}}\ x\notin S\end{matrix}}\right.}