帰納的分離不能対

計算可能性理論において帰納的分離不能対（きのうてきぶんりふのうつい、)とは自然数の集合の対で帰納的集合によって分離できないものをいう(Monk 1976, p. 100)。この概念は計算理論におけるΠ1集合と関係が深い。帰納的分離不能対はゲーデルの不完全性定理とも関係する。
定義.
自然数の集合を formula_1 とおく。互いに素な formula_2 の部分集合 formula_3 と formula_4 が与えられたとき、分離集合 formula_5 とは formula_2 の部分集合であって formula_7 かつ formula_8 (あるいは同じことだが formula_7 かつ formula_10)を満たすものをいう。例えば formula_3 はそれ自身と formula_12 との対の分離集合である。
互いに素な集合の対 formula_13 が帰納的分離集合を持たないとき帰納的分離不能であるという。
例.
もし集合 formula_3 が帰納的でないならば、 formula_15 とその補集合は帰納的分離不能である。しかしながら formula_3 と formula_4 が互いに素であり、互いに補集合でなく、帰納的分離不能であるような様々な formula_13 の例がある。さらには formula_13 が帰納的可算であるような例が存在する。
他方で任意の互いに素な補帰納的可算（Π1）集合の対は帰納的分離可能である。