単純集合のソースを表示

'''単純集合'''（たんじゅんしゅうごう、英：'''simple set'''）とは、[[数理論理学]]における[[再帰理論]]で扱われるある種の集合。[[帰納的可算集合|帰納的可算]]だが[[帰納的集合|帰納的]]ではない[[集合]]の例。

== ポストの問題との関係 ==

単純集合は[[エミール・ポスト]]によって[[チューリング還元|チューリング完全]]でなく再帰的でもない帰納的可算集合の研究の中で考案された。そのような集合が存在するかどうかは[[ポストの問題]]として知られる。ポストはこの問題の解答のために2つの事を証明する必要があった。ひとつは、単純集合は空集合に[[チューリング還元]]できないということである。いまひとつは、停止問題は単純集合にチューリング還元できないということである。彼が成功したのは前者であり（これは定義より明白）、後者は[[多対一還元]]についてのみ遂げられた。

このような集合が存在することは[[フリードバーグ]]と[[ムチニク]]により1950年に独立に証明された。そこでは[[優先法]]と呼ばれる手法が用いられた。彼らは単純だが停止性問題を還元できない集合の構成を与えた。<ref name=Nies35>Nies (2009) p.35</ref>

== 性質 ==
*集合 <math>I \subseteq \mathbb{N}</math> が'''免疫'''(immune)とは、<math>I</math> は無限集合であるが、任意の指標 <math>e</math> に対して <math>W_e \text{ infinite} \implies W_e \not\subseteq I</math> が成り立つことをいう。あるいは同じことであるが、<math>I</math> の無限部分集合で帰納的可算なものが存在しないことをいう。
*集合 <math>S \subseteq \mathbb{N}</math> が'''単純'''(simple)とは、それが帰納的可算であり、補集合が免疫であることをいう。あるいは同じことであるが <math>S</math> が補無限な帰納的可算集合であって、任意の帰納的可算な無限集合と交わることをいう。
*集合 <math>I \subseteq \mathbb{N}</math> が'''実効的免疫'''(effectively immune)とは、<math>I</math> は無限集合であるが、帰納的関数 <math>f</math> が存在して、任意の指標 <math>e</math> に対して <math> W_e \subseteq I \implies \#(W_e) < f(e)</math> が成り立つことをいう。
*集合 <math>S \subseteq \mathbb{N}</math> が'''実効的単純'''(effectively simple)とは、それが帰納的可算であり、補集合が実効的免疫であることをいう。任意の実効的単純集合は単純かつチューリング完全である。
*集合 <math>I \subseteq \mathbb{N}</math> が'''超免疫'''(hyper-immune)とは、<math>I</math> は無限集合であるが、<math>p_I</math> は計算可能な関数によって支配されないことをいう。ただし <math>p_I</math> は <math>I</math> の元を昇順に枚挙する関数である。<ref name=Nies27>Nies (2009) p.27</ref>
*集合 <math>S \subseteq \mathbb{N}</math> が'''超単純'''(hyper-simple)とは、それが帰納的可算であり、補集合が超免疫であることをいう。<ref name=Nies37>Nies (2009) p.37</ref>任意の超単純集合は単純である。

免疫集合の中には、補集合が同じく免疫であるものもある。このような集合の対は '''bi-immune'''<ref>訳注：「双免疫」などと訳すべきかも知れないが、定訳不明のため原語のまま</ref>と呼ばれる。bi-immune集合は（定義により帰納的可算ではないので）単純集合ではない。

==性質==

* 単純集合の集合と[[創造的集合と生産的集合|クリエイティブ集合]]の集合の和集合は交わりを持たない（[[合併 (集合論)|非交和]]）。単純集合がクリエイティブであることはなく、その逆もない。
* 集合がクリエイティブであることと[[多対一還元#多対一完全性（m-完全性）|m-完全]]であることとは同値である。ゆえに単純集合はm-完全でない。
* 単純または[[余有限]](cofinite)である集合の[[族 (数学)|系(collection)]]は、帰納的可算集合の[[束 (束論)|束]]の中で[[フィルター (数学)|フィルター]]を形成する。

==脚注==

<references/>

==参考文献==

* Robert I. Soare, ''Recursively Enumerable Sets and Degrees'', Springer-Verlag, 1987.	ISBN 0-387-15299-7

{{DEFAULTSORT:たんしゆんしゆうこう}}

[[Category:数理論理学]]
[[Category:計算可能性理論]]
[[Category:数学に関する記事]]