In computability theory

Computability theory

Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...

, recursively inseparable sets are pairs of sets of natural numbers that 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 Π⁰₁ 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 subsets A and B of ω, a separating set C is a subset of ω such that A ⊆ C and B ∩ C = ∅. For example, if A and B are disjoint then 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 recursively inseparable.

Examples

If A is any noncomputable 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 } and } are recursively inseparable (Gasarch 1998, p. 1047).
• Let # be a standard Gödel numbering for the formulas of Peano arithmetic. Then the set } of provable formulas and the set } 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).