シンプルなセット

計算可能性理論において、自然数の部分集合は、計算可能可算（ce）かつ余無限（すなわち、その補集合が無限）であるが、その補集合のすべての無限部分集合がceではない場合、単純集合と呼ばれます。単純集合は、計算不可能なce集合の例です。

ポストの問題との関係

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

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

正式な定義といくつかの特性

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

• 集合 が無限であるとき、その集合は免疫集合と呼ばれます。ただし、すべての添え字 に対してが成り立ちます。または、 ce となるの無限部分集合は存在しません。${\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} }$

注記

1. ニース（2009）35ページ
2. ニース（2009）p.27
3. ニース（2009）p.37

参考文献

• ソアレ、ロバート・I. (1987).再帰的に可算な集合と次数. 計算可能関数と計算可能生成集合の研究. 数理論理学の展望. ベルリン:シュプリンガー・フェアラーク. ISBN 3-540-15299-7. Zbl  0667.03030 .
• オディフレッディ、ピエールジョルジオ(1988).古典的再帰理論. 関数と自然数集合の理論. 論理学と数学の基礎研究. 第125巻. アムステルダム: 北ホラント. ISBN 0-444-87295-7. Zbl  0661.03029 .
• ニース、アンドレ（2009）『計算可能性とランダム性』オックスフォード・ロジック・ガイド第51巻、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-923076-1. Zbl  1169.03034 .