単純集合

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

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

• 集合 ${\displaystyle I\subseteq \mathbb {N} }$ が免疫(immune)とは、${\displaystyle I}$ は無限集合であるが、任意の指標 ${\displaystyle e}$ に対して ${\displaystyle W_{e}{\text{ infinite}}\implies W_{e}\not \subseteq I}$ が成り立つことをいう。あるいは同じことであるが、${\displaystyle I}$ の無限部分集合で帰納的可算なものが存在しないことをいう。
• 集合 ${\displaystyle S\subseteq \mathbb {N} }$ が単純(simple)とは、それが帰納的可算であり、補集合が免疫であることをいう。あるいは同じことであるが ${\displaystyle S}$ が補無限な帰納的可算集合であって、任意の帰納的可算な無限集合と交わることをいう。
• 集合 ${\displaystyle I\subseteq \mathbb {N} }$ が実効的免疫(effectively immune)とは、${\displaystyle I}$ は無限集合であるが、帰納的関数 ${\displaystyle f}$ が存在して、任意の指標 ${\displaystyle e}$ に対して ${\displaystyle W_{e}\subseteq I\implies \#(W_{e})<f(e)}$ が成り立つことをいう。
• 集合 ${\displaystyle S\subseteq \mathbb {N} }$ が実効的単純(effectively simple)とは、それが帰納的可算であり、補集合が実効的免疫であることをいう。任意の実効的単純集合は単純かつチューリング完全である。
• 集合 ${\displaystyle I\subseteq \mathbb {N} }$ が超免疫(hyper-immune)とは、${\displaystyle I}$ は無限集合であるが、${\displaystyle p_{I}}$ は計算可能な関数によって支配されないことをいう。ただし ${\displaystyle p_{I}}$ は ${\displaystyle I}$ の元を昇順に枚挙する関数である。^[2]
• 集合 ${\displaystyle S\subseteq \mathbb {N} }$ が超単純(hyper-simple)とは、それが帰納的可算であり、補集合が超免疫であることをいう。^[3]任意の超単純集合は単純である。

免疫集合の中には、補集合が同じく免疫であるものもある。このような集合の対は bi-immune^[4]と呼ばれる。bi-immune集合は（定義により帰納的可算ではないので）単純集合ではない。