単純集合
単純集合はエミール・ポストによってチューリング完全でなく再帰的でもない帰納的可算集合の研究の中で考案された。そのような集合が存在するかどうかはポストの問題として知られる。ポストはこの問題の解答のために2つの事を証明する必要があった。ひとつは、単純集合は空集合にチューリング還元できないということである。いまひとつは、停止問題は単純集合にチューリング還元できないということである。彼が成功したのは前者であり(これは定義より明白)、後者は多対一還元についてのみ遂げられた。
このような集合が存在することはフリードバーグとムチニクにより1950年に独立に証明された。そこでは優先法と呼ばれる手法が用いられた。彼らは単純だが停止性問題を還元できない集合の構成を与えた。
集合 S ⊆ N {\displaystyle S\subseteq \mathbb {N} } が実効的単純(effectively simple)とは、それが帰納的可算であり、補集合が実効的免疫であることをいう。任意の実効的単純集合は単純かつチューリング完全である。
集合 I ⊆ N {\displaystyle I\subseteq \mathbb {N} } が超免疫(hyper-immune)とは、 I {\displaystyle I} は無限集合であるが、 p I {\displaystyle p_{I}} は計算可能な関数によって支配されないことをいう。ただし p I {\displaystyle p_{I}} は I {\displaystyle I} の元を昇順に枚挙する関数である。
集合 S ⊆ N {\displaystyle S\subseteq \mathbb {N} } が超単純(hyper-simple)とは、それが帰納的可算であり、補集合が超免疫であることをいう。任意の超単純集合は単純である。
免疫集合の中には、補集合が同じく免疫であるものもある。このような集合の対は bi-immuneと呼ばれる。bi-immune集合は(定義により帰納的可算ではないので)単純集合ではない。
単純集合の集合とクリエイティブ集合の集合の和集合は交わりを持たない(非交和)。単純集合がクリエイティブであることはなく、その逆もない。
集合がクリエイティブであることとm-完全であることとは同値である。ゆえに単純集合はm-完全でない。
単純または余有限(cofinite)である集合の系(collection)は、帰納的可算集合の束の中でフィルターを形成する。