帰納的分離不能対

もし集合 ${\displaystyle A}$ が帰納的でないならば、 ${\displaystyle a}$ とその補集合は帰納的分離不能である。しかしながら ${\displaystyle A}$ と ${\displaystyle B}$ が互いに素であり、互いに補集合でなく、帰納的分離不能であるような様々な ${\displaystyle (A,B)}$ の例がある。さらには ${\displaystyle (A,B)}$ が帰納的可算であるような例が存在する。

• ${\displaystyle \varphi }$ を部分計算可能関数の標準的なナンバリングとする。このとき ${\displaystyle \{e|\psi _{e}(e)=0\}}$ と ${\displaystyle \{e|\psi _{e}(e)=1\}}$ とは帰納的分離不能である(Gasarch 1998, p. 1047)。
• ${\displaystyle \sharp }$ をロビンソン算術の論理式の標準的なゲーデルナンバリングとする。このとき定理の集合 ${\displaystyle \{\sharp \varphi |Q\vdash \varphi \}}$ と反定理の集合 ${\displaystyle \{\sharp \varphi |Q\vdash \neg \varphi \}}$ は帰納的分離不能である。この事実はロビンソン算術の本質的決定不可能性を導く。他の多くの算術の形式的体系においても同様にして帰納的分離不能対が得られる(Smullyan 1958)。

他方で任意の互いに素な補帰納的可算（Π₁）集合の対は帰納的分離可能である。

• Cenzer, Douglas (1999), “Π0
  1 classes in computability theory”, Handbook of computability theory, Stud. Logic Found. Math., 140, Amsterdam: North-Holland, pp. 37–85, MR1720779 
• Gasarch, William (1998), “A survey of recursive combinatorics”, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., 139, Amsterdam: North-Holland, pp. 1041–1176, MR1673598 
• Monk, J. Donald (1976), Mathematical Logic, Graduate Texts in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-0-387-90170-1 
• Smullyan, Raymond M. (1958), “Undecidability and recursive inseparability”, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 4: 143–147, doi:10.1002/malq.19580040705, ISSN 0044-3050, MR0099293 

• 帰納的可算集合
• 算術的階層
• 創造的集合