単純集合

単純集合（たんじゅんしゅうごう、英：simple set）とは、数理論理学における再帰理論で扱われるある種の集合。帰納的可算だが帰納的ではない集合の例。
ポストの問題との関係.
単純集合はエミール・ポストによってチューリング完全でなく再帰的でもない帰納的可算集合の研究の中で考案された。そのような集合が存在するかどうかはポストの問題として知られる。ポストはこの問題の解答のために2つの事を証明する必要があった。ひとつは、単純集合は空集合にチューリング還元できないということである。いまひとつは、停止問題は単純集合にチューリング還元できないということである。彼が成功したのは前者であり（これは定義より明白）、後者は多対一還元についてのみ遂げられた。
このような集合が存在することはフリードバーグとムチニクにより1950年に独立に証明された。そこでは優先法と呼ばれる手法が用いられた。彼らは単純だが停止性問題を還元できない集合の構成を与えた。
性質.
免疫集合の中には、補集合が同じく免疫であるものもある。このような集合の対は bi-immuneと呼ばれる。bi-immune集合は（定義により帰納的可算ではないので）単純集合ではない。