Computably inseparable

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. These sets arise in the study of computability theory itself, particularly in relation to [math]\displaystyle{ \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]\displaystyle{ \mathbb{N} = \{0, 1, 2, \dots\} }[/math]. Given disjoint subsets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] of [math]\displaystyle{ \mathbb{N} }[/math], a separating set [math]\displaystyle{ C }[/math] is a subset of [math]\displaystyle{ \mathbb{N} }[/math] such that [math]\displaystyle{ A \subseteq C }[/math] and [math]\displaystyle{ B \cap C = \emptyset }[/math] (or equivalently, [math]\displaystyle{ A \subseteq C }[/math] and [math]\displaystyle{ B \subseteq C' }[/math], where [math]\displaystyle{ C' = \mathbb{N} \setminus C }[/math] denotes the complement of [math]\displaystyle{ C }[/math]). For example, [math]\displaystyle{ A }[/math] itself is a separating set for the pair, as is [math]\displaystyle{ B' }[/math].

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

Examples

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

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

• Cenzer, Douglas (1999), "Π01 classes in computability theory", Handbook of computability theory, Stud. Logic Found. Math., 140, Amsterdam: North-Holland, pp. 37–85, doi:10.1016/S0049-237X(99)80018-4 
• Gasarch, William (1998), "A survey of recursive combinatorics", Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., 139, Amsterdam: North-Holland, pp. 1041–1176, doi:10.1016/S0049-237X(98)80049-9 
• Monk, J. Donald (1976), Mathematical Logic, Graduate Texts in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-0-387-90170-1, https://archive.org/details/mathematicallogi00jdon 
• 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