帰納的分離不能対

計算可能性理論において帰納的分離不能対（きのうてきぶんりふのうつい、英: recursively inseparable pair)とは自然数の集合の対で帰納的集合によって分離できないものをいう(Monk 1976, p. 100)。この概念は計算理論におけるΠ₁集合と関係が深い。帰納的分離不能対はゲーデルの不完全性定理とも関係する。

定義

自然数の集合を $\omega =\{0,1,2,\ldots \}$ とおく。互いに素な $\omega$ の部分集合 $A$ と $B$ が与えられたとき、分離集合 $C$ とは $\omega$ の部分集合であって $A\subseteq C$ かつ $B\cap C=\varnothing$ (あるいは同じことだが $A\subseteq C$ かつ $B\subseteq \omega \setminus C$ )を満たすものをいう。例えば $A$ はそれ自身と $\omega \setminus B$ との対の分離集合である。

互いに素な集合の対 $(A,B)$ が帰納的分離集合を持たないとき帰納的分離不能であるという。

例

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

$\varphi$ を部分計算可能関数の標準的なナンバリングとする。このとき $\{e|\psi _{e}(e)=0\}$ と $\{e|\psi _{e}(e)=1\}$ とは帰納的分離不能である(Gasarch 1998, p. 1047)。
$\sharp$ をロビンソン算術の論理式の標準的なゲーデルナンバリングとする。このとき定理の集合 $\{\sharp \varphi |Q\vdash \varphi \}$ と反定理の集合 $\{\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, MR 1720779
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

定義

例

参考文献

関連項目