シンプルセット

計算可能性理論では、自然数のサブセットが計算可能列挙可能(ce) かつ共無限 (つまり、その補集合が無限)であるが、その補集合のすべての無限サブセットが ce ではない場合、そのサブセットは単純であると呼ばれます。単純集合は、計算可能でない ce 集合の例です。

単純集合は、チューリング完全でない集合を探す中でエミール・レオン・ポストによって考案されました。そのような集合が存在するかどうかは、ポストの問題として知られています。ポストは、その結果を得るために、単純集合Aが計算可能でないこと、および停止問題KがAにチューリング還元されないことの 2 つを証明する必要がありました。彼は最初の部分 (定義により明らか) では成功しましたが、他の部分では、多対一還元しか証明できませんでした。

ポストのアイデアは、1950年代にフリードバーグとムチニックによって、優先権法と呼ばれる新しい手法を使用して検証されました。彼らは、単純な（したがって計算不可能な）集合の構成を与えましたが、停止問題を計算できませんでした。^[1]

以下では、すべての ce セットの標準的な均一な ce リストを示します。 ${\displaystyle W_{e}}$

• が無限である集合は免疫集合と呼ばれますが、すべての添え字 に対して が成り立ちます。または、同等に、である の無限部分集合は存在しません。${\displaystyle I\subseteq \mathbb {N} }$${\displaystyle I}$${\displaystyle e}$${\displaystyle W_{e}{\text{ 無限}}\implies W_{e}\not \subseteq I}$${\displaystyle I}$
• ある集合が ce であり、その補集合が免疫集合である場合、その集合は単純であると呼ばれます。${\displaystyle S\subseteq \mathbb {N} }$
• が無限であるが、すべてのインデックス に対して となるような再帰関数が存在する場合、その集合は事実上免疫があると呼ばれます。${\displaystyle I\subseteq \mathbb {N} }$${\displaystyle I}$${\displaystyle f}$${\displaystyle e}$${\displaystyle W_{e}\subseteq I\implies \#(W_{e})<f(e)}$
• ある集合が ce であり、その補集合が事実上免疫である場合、その集合は事実上単純であると呼ばれます。すべての事実上単純な集合は単純かつチューリング完全です。${\displaystyle S\subseteq \mathbb {N} }$
• 集合が無限であるが計算上支配されず、集合の要素の順序のリストである場合、その集合は超免疫集合と呼ばれます。^[2]${\displaystyle I\subseteq \mathbb {N} }$${\displaystyle I}$${\displaystyle p_{I}}$${\displaystyle p_{I}}$${\displaystyle I}$
• ある集合が単純であり、その補集合が超免疫的である場合、その集合は超単純と呼ばれる。 ^[3]${\displaystyle S\subseteq \mathbb {N} }$

• Soare, Robert I. (1987)。再帰的に列挙可能な集合と次数。計算可能関数と計算可能生成集合の研究。数理論理学の展望。ベルリン: Springer- Verlag。ISBN 3-540-15299-7.ZBL0667.03030  。​
• オディフレッディ、ピエールジョルジオ(1988)。古典的再帰理論。関数と自然数の集合の理論。論理学と数学の基礎研究。第 125 巻。アムステルダム: 北ホラント。ISBN 0-444-87295-7.ZBL0661.03029  。​
• ニース、アンドレ (2009)。計算可能性とランダム性。オックスフォードロジックガイド。第51巻。オックスフォード：オックスフォード大学出版局。ISBN 978-0-19-923076-1.ZBL1169.03034  。​