帰納的分離不能対
1047)。
♯ {\displaystyle \sharp } をロビンソン算術の論理式の標準的なゲーデルナンバリングとする。このとき定理の集合 { ♯ φ | Q ⊢ φ } {\displaystyle \{\sharp \varphi |Q\vdash \varphi \}} と反定理の集合 { ♯ φ | Q ⊢ ¬ φ } {\displaystyle \{\sharp \varphi |Q\vdash \neg \varphi \}} は帰納的分離不能である。この事実はロビンソン算術の本質的決定不可能性を導く。他の多くの算術の形式的体系においても同様にして帰納的分離不能対が得られる(Smullyan 1958)。
他方で任意の互いに素な補帰納的可算(Π1)集合の対は帰納的分離可能である。
計算可能性理論において帰納的分離不能対(きのうてきぶんりふのうつい、英: recursively inseparable pair)とは自然数の集合の対で帰納的集合によって分離できないものをいう(Monk 1976, p. 100)。この概念は計算理論におけるΠ1集合と関係が深い。帰納的分離不能対はゲーデルの不完全性定理とも関係する。