Recursively inseparable sets

In computability theory, recursively inseparable sets are pairs of sets of natural numbers that cannot be "separated" with a recursive set (Monk 1976, p. 100). These sets arise in the study of computability theory itself, particularly in relation to Π0
1 classes. Recursively inseparable sets also arise in the study of Gödel's incompleteness theorem.

Definition

The natural numbers are the set ω = {0, 1, 2, ...}. Given disjoint subsets A and B of ω, a separating set C is a subset of ω such that A ⊆ C and B ∩ C = ∅ (or equivalently, A ⊆ C and B ⊆ 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 recursive separating set, then the two sets are recursively inseparable.

Examples

If A is a non-recursive set then A and its complement are recursively inseparable. However, there are many examples of sets A and B that are disjoint, non-complementary, and recursively inseparable. Moreover, it is possible for A and B to be recursively inseparable, disjoint, and recursively 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 recursively inseparable (William Gasarch1998, p. 1047).
• Let # be a standard Gödel numbering for the formulas of Peano arithmetic. Then the set A = { #(ψ) : PA ⊢ ψ} of provable formulas and the set B = { #(ψ) : PA ⊢ ¬ψ} of refutable formulas are recursively 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), "Π0
  1 classes in computability theory", Handbook of computability theory, Stud. Logic Found. Math. 140, Amsterdam: North-Holland, pp. 37–85, MR 1720779
• 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, 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: 143–147, doi:10.1002/malq.19580040705, ISSN 0044-3050, MR 0099293