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.Monk 1976, p. 100 These sets arise in the study of computability theory itself, particularly in relation to $\Pi^0_1$ classes. Computably inseparable sets also arise in the study of Gödel's incompleteness theorem.

Definition

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

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

Examples

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

Let $\varphi$ be the standard indexing of the partial computable functions. Then the sets $A = \{ e : \varphi_e(0) = 0 \}$ and $B = \{ e : \varphi_e(0) = 1 \}$ are computably inseparable (William Gasarch1998, p. 1047).
Let $\#$ be a standard Gödel numbering for the formulas of Peano arithmetic. Then the set $A = \{ \#(\psi) : PA \vdash \psi \}$ of provable formulas and the set $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).

References

{{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