帰納的分離不能対のソースを表示

[[計算可能性理論]]において'''帰納的分離不能対'''（きのうてきぶんりふのうつい、{{lang-en-short|recursively inseparable pair}})とは自然数の集合の対で[[帰納的集合]]によって'''分離'''できないものをいう(Monk 1976, p.&nbsp;100)。この概念は計算理論における[[算術的階層|&Pi;<sub>1</sub>集合]]と関係が深い。帰納的分離不能対は[[ゲーデルの不完全性定理]]とも関係する。

== 定義 ==

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

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

== 例 ==

もし集合 <math>A</math> が帰納的でないならば、 <math>a</math> とその補集合は帰納的分離不能である。しかしながら <math>A</math> と <math>B</math> が互いに素であり、互いに補集合でなく、帰納的分離不能であるような様々な <math>(A, B)</math> の例がある。さらには <math>(A, B)</math> が[[帰納的可算]]であるような例が存在する。
* <math>\varphi</math> を部分計算可能関数の標準的な[[ナンバリング_(計算可能性理論)|ナンバリング]]とする。このとき <math>\{ e | \psi_e(e) = 0 \}</math> と <math>\{ e | \psi_e(e) = 1 \}</math> とは帰納的分離不能である(Gasarch 1998, p.&nbsp;1047)。
* <math>\sharp</math> を[[ロビンソン算術]]の論理式の標準的な[[ゲーデル数|ゲーデルナンバリング]]とする。このとき定理の集合 <math>\{ \sharp\varphi | Q \vdash \varphi \}</math> と反定理の集合 <math>\{ \sharp\varphi | Q \vdash \neg\varphi \}</math> は帰納的分離不能である。この事実はロビンソン算術の[[本質的決定不可能性]]を導く。他の多くの算術の形式的体系においても同様にして帰納的分離不能対が得られる(Smullyan 1958)。

他方で任意の互いに素な補帰納的可算（&Pi;<sub>1</sub>）集合の対は帰納的分離可能である。

== 参考文献 ==
* {{Citation | last1=Cenzer | first1=Douglas | title=Handbook of computability theory | publisher=North-Holland | location=Amsterdam | series=Stud. Logic Found. Math. |mr=1720779 | year=1999 | volume=140 | chapter=Π{{su|p=0|b=1}} classes in computability theory | pages=37–85}}
* {{Citation | last1=Gasarch | first1=William | title=Handbook of recursive mathematics, Vol. 2 | publisher=North-Holland | location=Amsterdam | series=Stud. Logic Found. Math. |mr=1673598 | year=1998 | volume=139 | chapter=A survey of recursive combinatorics | pages=1041–1176}}
* {{Citation | last1=Monk | first1=J. Donald | title=Mathematical Logic | publisher=[[Springer-Verlag]] | location=Berlin, New York | series=Graduate Texts in Mathematics | isbn=978-0-387-90170-1 | year=1976}}
* {{Citation | last1=Smullyan | first1=Raymond M. | author1-link=Raymond M. Smullyan | title=Undecidability and recursive inseparability | doi=10.1002/malq.19580040705 |mr=0099293 | year=1958 | journal=Zeitschrift für Mathematische Logik und Grundlagen der Mathematik | issn=0044-3050 | volume=4 | pages=143–147}}

== 関連項目 ==
* [[帰納的可算集合]]
* [[算術的階層]]
* [[創造的集合]]

[[Category:計算可能性理論]]

{{DEFAULTSORT:さいきてきふんりふのうつい}}