単純集合

単純集合とは

単純集合（たんじゅんしゅうごう、英：simple set）は、数理論理学の再帰理論において非常に特異な集合の一種です。この集合は、帰納的可算であるものの帰納的では無いという特徴があります。そのため、単純集合はコンピュータ科学や数学において重要な研究対象となっています。

ポストの問題との関連

単純集合はエミール・ポストによって考案されました。彼は、チューリング完全でなく再帰的でもない帰納的可算集合についての研究を行い、その中で単純集合が登場します。ポストの問題とは、このような特異な集合が存在するのかどうかを問うものであり、その解決にはいくつかの証明が必要でした。

ポストが解決すべきだったのは、単純集合は空集合にチューリング還元できないこと、また、停止問題は単純集合に対してチューリング還元できないということです。前者については明らかであり、後者に関しては多対一還元についてのみ証明が成功しました。1950年には、フリードバーグとムチニクが独立にこのような集合の存在を証明しました。彼らは優先法という手法を用い、単純だが停止性問題を還元できない集合を構成しました。

集合の性質

単純集合にはいくつかの重要な性質があります。まず、集合が免疫（immune）であるとは、無限集合であって、任意の指標に対して特定の条件が成り立つことを意味します。具体的には、無限集合である I に対して、任意の指標 e に対して、もし W_e が無限であるならば、W_e は I に含まれないという条件です。また、I の無限部分集合が帰納的可算なものを持たない場合も同様に免疫とされます。

単純集合 S は、帰納的可算であり、補集合が免疫であることを特徴とします。この特性により、S は補無限な帰納的可算集合であり、任意の帰納的可算な無限集合に交わります。また、実効的免疫や実効的単純といった概念も関連しており、これらは単純集合の理解に重要です。

もう一つの関連する概念は超免疫（hyper-immune）で、これは I が無限集合でありながら、特定の関数によって支配されないことを意味します。超単純（hyper-simple）集合は、単純集合であり、補集合が超免疫となる特性を持ちます。

免疫の関係

免疫集合の中には、補集合も同じく免疫であるケースがあり、これらの両者は bi-immune と呼ばれます。ただし、bi-immune 集合は帰納的可算でないため、単純集合には該当しません。また、単純集合の集合とクリエイティブ集合の集合の和集合には交わりが無いことが知られています。

結論

一般的に、単純集合はその特異性により数理論理学における重要な研究対象であり、ポストの問題やその性質についての深い理解が必要とされています。その研究を通して、計算可能性や帰納的可算集合の特性についての洞察が得られるのです。

もう一度検索