計算上分離不可能

計算可能性理論では、自然数の互いに素な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'}$

互いに素な集合のペアとに計算可能な分離集合がない場合、2 つの集合は計算可能に分離不可能です。 ${\displaystyle A}$${\displaystyle B}$

が計算不可能な集合である場合、 とその補集合は計算可能分離不可能です。しかし、互いに素で、互いに補集合でなく、かつ計算可能分離不可能である集合との例は数多くあります。さらに、と が計算可能分離可能、互いに素、かつ計算可能列挙可能であることは可能です。 ${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$

• を部分計算可能関数の標準的なインデックスとします。このとき、集合と は計算可能的に分離不可能です ( William Gasarch 1998、p. 1047)。${\displaystyle \varphi}$${\displaystyle A=\{e:\varphi _{e}(0)=0\}}$${\displaystyle B=\{e:\varphi _{e}(0)=1\}}$
• をペアノ算術の公式の標準的なゲーデル数とします。このとき、証明可能な公式の集合と反証可能な公式の集合は計算的に分離不可能です。証明可能な公式と反証可能な公式の集合の分離不可能性は、算術の他の多くの形式理論にも当てはまります (Smullyan 1958)。${\displaystyle \#}$${\displaystyle A=\{\#(\psi ):PA\vdash \psi \}}$${\displaystyle B=\{\#(\psi ):PA\vdash \lnot \psi \}}$

• センザー、ダグラス（1999）「Π⁰
  ₁計算可能性理論のクラス」、計算可能性理論ハンドブック、Stud. Logic Found. Math.、vol. 140、アムステルダム：北ホラント、pp. 37–85、doi：10.1016/S0049-237X（99）80018-4、MR  1720779
• ガサーチ、ウィリアム(1998)、「再帰的組合せ論の概観」、再帰的数学ハンドブック、第 2 巻、Stud. Logic Found. Math.、第 139 巻、アムステルダム: 北ホラント、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