{{Short description|Concept in computability theory}} 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]].<ref>Monk 1976, p. 100</ref> These sets arise in the study of computability theory itself, particularly in relation to [[Pi01 class|<math>\Pi^0_1</math> classes]]. Computably inseparable sets also arise in the study of [[Gödel's incompleteness theorem]].
== Definition ==
The natural numbers are the set <math>\mathbb{N} = \{0, 1, 2, \dots\}</math>. Given disjoint subsets <math> A </math> and <math> B</math> of <math>\mathbb{N}</math>, a '''separating set''' <math> C </math> is a subset of <math>\mathbb{N}</math> such that <math>A \subseteq C</math> and <math>B \cap C = \emptyset</math> (or equivalently, <math>A \subseteq C</math> and <math>B \subseteq C'</math>, where <math>C' = \mathbb{N} \setminus C</math> denotes the [[complement (set theory)|complement]] of <math>C</math>). For example, <math>A</math> itself is a [[separating set]] for the pair, as is <math>B'</math>.
If a pair of disjoint sets <math>A</math> and <math>B</math> has no [[Computable set|computable]] separating set, then the two sets are '''computably inseparable'''.
== Examples ==
If <math>A</math> is a non-computable set, then <math>A</math> and its complement are computably inseparable. However, there are many examples of sets <math>A</math> and <math>B </math> that are disjoint, non-complementary, and computably inseparable. Moreover, it is possible for <math>A</math> and <math>B</math> to be computably inseparable, disjoint, and [[computably enumerable]]. * Let <math>\varphi</math> be the standard indexing of the [[partial computable function]]s. Then the sets <math>A = \{ e : \varphi_e(0) = 0 \}</math> and <math>B = \{ e : \varphi_e(0) = 1 \}</math> are computably inseparable ([[William Gasarch]]1998, p. 1047). * Let <math>\#</math> be a standard [[Gödel numbering]] for the formulas of [[Peano arithmetic]]. Then the set <math>A = \{ \#(\psi) : PA \vdash \psi \}</math> of provable formulas and the set <math>B = \{ \#(\psi) : PA \vdash \lnot\psi \}</math> 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).
== References == {{Reflist}} * {{Citation | last1=Cenzer | first1=Douglas | title=Handbook of computability theory | publisher=North-Holland | location=Amsterdam | series=Stud. Logic Found. Math. |mr=1720779 | year=1999 | volume=140 | chapter=Π{{su|p=0|b=1}} classes in computability theory | pages=37–85 | doi=10.1016/S0049-237X(99)80018-4}} * {{Citation | last1=Gasarch | first1=William | author1-link=William Gasarch | title=Handbook of recursive mathematics, Vol. 2 | publisher=North-Holland | location=Amsterdam | series=Stud. Logic Found. Math. |mr=1673598 | year=1998 | volume=139 | chapter=A survey of recursive combinatorics | pages=1041–1176 | doi=10.1016/S0049-237X(98)80049-9}} * {{Citation | last1=Monk | first1=J. Donald | title=Mathematical Logic | publisher=[[Springer-Verlag]] | location=Berlin, New York | series=Graduate Texts in Mathematics | isbn=978-0-387-90170-1 | year=1976 | url-access=registration | url=https://archive.org/details/mathematicallogi00jdon }} * {{Citation | last1=Smullyan | first1=Raymond M. | author1-link=Raymond M. Smullyan | title=Undecidability and recursive inseparability | doi=10.1002/malq.19580040705 |mr=0099293 | year=1958 | journal=Zeitschrift für Mathematische Logik und Grundlagen der Mathematik | issn=0044-3050 | volume=4 | issue=7–11 | pages=143–147}}
[[Category:Computability theory]]