Computably inseparable

In computability theory, two disjoint sets of natural numbers are called computably inseparable or recursively inseparable if they cannot be "separated" with a computable set.^[1] These sets arise in the study of computability theory itself, particularly in relation to ${\displaystyle \Pi _{1}^{0}}${\displaystyle \Pi _{1}^{0}} classes. Computably inseparable sets also arise in the study of Gödel's incompleteness theorem.

The natural numbers are the set ${\displaystyle \mathbb {N} =\{0,1,2,\dots \}}${\displaystyle \mathbb {N} =\{0,1,2,\dots \}}. Given disjoint subsets ${\displaystyle A}${\displaystyle A} and ${\displaystyle B}${\displaystyle B} of ${\displaystyle \mathbb {N} }${\displaystyle \mathbb {N} }, a separating set ${\displaystyle C}${\displaystyle C} is a subset of ${\displaystyle \mathbb {N} }${\displaystyle \mathbb {N} } such that ${\displaystyle A\subseteq C}${\displaystyle A\subseteq C} and ${\displaystyle B\cap C=\emptyset }${\displaystyle B\cap C=\emptyset } (or equivalently, ${\displaystyle A\subseteq C}${\displaystyle A\subseteq C} and ${\displaystyle B\subseteq C'}${\displaystyle B\subseteq C'}, where ${\displaystyle C'=\mathbb {N} \setminus C}${\displaystyle C'=\mathbb {N} \setminus C} denotes the complement of ${\displaystyle C}${\displaystyle C}). For example, ${\displaystyle A}${\displaystyle A} itself is a separating set for the pair, as is ${\displaystyle B'}${\displaystyle B'}.

If a pair of disjoint sets ${\displaystyle A}${\displaystyle A} and ${\displaystyle B}${\displaystyle B} has no computable separating set, then the two sets are computably inseparable.

If ${\displaystyle A}${\displaystyle A} is a non-computable set, then ${\displaystyle A}${\displaystyle A} and its complement are computably inseparable. However, there are many examples of sets ${\displaystyle A}${\displaystyle A} and ${\displaystyle B}${\displaystyle B} that are disjoint, non-complementary, and computably inseparable. Moreover, it is possible for ${\displaystyle A}${\displaystyle A} and ${\displaystyle B}${\displaystyle B} to be computably inseparable, disjoint, and computably enumerable.

• Let ${\displaystyle \varphi }${\displaystyle \varphi } be the standard indexing of the partial computable functions. Then the sets ${\displaystyle A=\{e:\varphi _{e}(0)=0\}}${\displaystyle A=\{e:\varphi _{e}(0)=0\}} and ${\displaystyle B=\{e:\varphi _{e}(0)=1\}}${\displaystyle B=\{e:\varphi _{e}(0)=1\}} are computably inseparable (William Gasarch1998, p. 1047).
• Let ${\displaystyle \#}${\displaystyle \#} be a standard Gödel numbering for the formulas of Peano arithmetic. Then the set ${\displaystyle A=\{\#(\psi ):PA\vdash \psi \}}${\displaystyle A=\{\#(\psi ):PA\vdash \psi \}} of provable formulas and the set ${\displaystyle B=\{\#(\psi ):PA\vdash \lnot \psi \}}${\displaystyle B=\{\#(\psi ):PA\vdash \lnot \psi \}} of refutable formulas are computably inseparable. The inseparability of the sets of provable and refutable formulas holds for many other formal theories of arithmetic (Smullyan 1958).

• Cenzer, Douglas (1999), "Π⁰
  ₁ classes in computability theory", Handbook of computability theory, Stud. Logic Found. Math., vol. 140, Amsterdam: North-Holland, pp. 37–85, doi:10.1016/S0049-237X(99)80018-4, MR 1720779
• Gasarch, William (1998), "A survey of recursive combinatorics", Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, Amsterdam: North-Holland, pp. 1041–1176, doi:10.1016/S0049-237X(98)80049-9, MR 1673598
• Monk, J. Donald (1976), Mathematical Logic , Graduate Texts in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-0-387-90170-1
• Smullyan, Raymond M. (1958), "Undecidability and recursive inseparability", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 4 (7–11): 143–147, doi:10.1002/malq.19580040705, ISSN 0044-3050, MR 0099293

• Computability theory

• Articles with short description
• Short description is different from Wikidata