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. These sets arise in the study of computability theory itself, particularly in relation to $Π_{1}^{0}$ classes. Computably inseparable sets also arise in the study of Gödel's incompleteness theorem.

Definition

The natural numbers are the set $ℕ = {0, 1, 2, \dots}$ . Given disjoint subsets $A$ and $B$ of $ℕ$ , a separating set $C$ is a subset of $ℕ$ such that $A \subseteq C$ and $B \cap C = ∅︀$ (or equivalently, $A \subseteq C$ and $B \subseteq C^{'}$ , where $C^{'} = ℕ ∖ 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 $φ$ be the standard indexing of the partial computable functions. Then the sets $A = {e : φ_{e} (0) = 0}$ and $B = {e : φ_{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 = {# (ψ) : P A ⊢ ψ}$ of provable formulas and the set $B = {# (ψ) : P A ⊢ \neg ψ}$ 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

↑ Monk 1976, p. 100

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

[1] Monk 1976, p. 100