計算上分離不可能

計算可能性理論において、互いに素な自然数の集合2つは、計算可能な集合で「分離」できない場合、計算不可能または再帰的に分離不可能と呼ばれます。^{[ 1 ]} これらの集合は、計算可能性理論自体の研究、特に、$\displaystyle \Pi _{1}^{0}}$クラス。計算不可能な集合は、ゲーデルの不完全性定理の研究でも出現する。

自然数は集合である${\displaystyle \mathbb {N} =\{0,1,2,\dots \}}$互いに素な部分集合が与えられた場合${\displaystyle A}$そして${\displaystyle B}$の${\displaystyle \mathbb {N} }$分離セット${\displaystyle C}$は、${\displaystyle \mathbb {N} }$そのため ${\displaystyle A\subseteq C}$そして${\displaystyle B\cap C=\emptyset }$（または同等に、 ${\displaystyle A\subseteq C}$そして${\displaystyle B\subseteq C'}$、 どこ${\displaystyle C'=\mathbb {N} \setminus C}$の補数を表す${\displaystyle C}$）。 例えば、${\displaystyle A}$それ自体はペアの分離セットであり、${\displaystyle B'}$。

互いに素な集合のペアの場合${\displaystyle A}$そして${\displaystyle B}$計算可能な分離集合を持たない場合、2 つの集合は計算上分離不可能である。

もし${\displaystyle A}$は計算不可能な集合である。${\displaystyle A}$集合とその補集合は計算上分離不可能である。しかし、集合の例は数多く存在する。${\displaystyle A}$そして${\displaystyle B}$互いに排他的で、相補的ではなく、計算上分離不可能なものである。さらに、${\displaystyle A}$そして${\displaystyle B}$計算上分離不可能であり、互いに排他的であり、計算上列挙可能であること。

• させて${\displaystyle \varphi }$部分計算可能関数の標準インデックスとする。すると、集合は${\displaystyle A=\{e:\varphi _{e}(0)=0\}}$そして${\displaystyle B=\{e:\varphi _{e}(0)=1\}}$それらは計算上分離不可能である（ウィリアム・ガサーチ1998、p.  1047）。
• させて${\displaystyle \#}$ペアノ算術の公式に対する標準的なゲーデル番号付けとする。すると、集合は${\displaystyle A=\{\#(\psi ):PA\vdash \psi \}}$証明可能な公式と集合${\displaystyle B=\{\#(\psi ):PA\vdash \lnot \psi \}}$反証可能な公式の集合は計算上分離不可能である。証明可能な公式の集合と反証可能な公式の集合の分離不可能性は、他の多くの形式的な算術理論にも当てはまる（Smullyan 1958）。

• Cenzer, Douglas (1999)、「計算可能性理論におけるΠ ⁰ ₁クラス」、計算可能性理論ハンドブック、Stud. Logic Found. Math.、第 140巻、アムステルダム：North-Holland、pp. 37–85、doi：10.1016/S0049-237X(99)80018-4、MR 1720779  
• Gasarch, William (1998)、「再帰的組み合わせ論の概観」、再帰的数学ハンドブック、第2巻、Stud. Logic Found. Math.、第 139巻、アムステルダム：North-Holland、pp. 1041–1176、doi：10.1016/S0049-237X(98)80049-9、MR 1673598  
• モンク、J.ドナルド（1976）、『数理論理学』、大学院数学テキスト、ベルリン、ニューヨーク：シュプリンガー・フェルラーク、ISBN 978-0-387-90170-1
• Smullyan、Raymond M. (1958)、「決定不可能性と再帰的不可分性」、Zeitschrift für Mathematische Logik und Grundlagen der Mathematik、4 ( 7–11 ): 143–147、doi : 10.1002/malq.19580040705、ISSN 0044-3050、MR 0099293