# Computably inseparable

(Redirected from Effectively separable)

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 Π0
1
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, ...}. Given disjoint subsets A and B of ω, a separating set C is a subset of ω such that AC and BC = ∅ (or equivalently, AC and BC). 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 = { #(ψ) : PA ⊢ ψ} of provable formulas and the set B = { #(ψ) : PA ⊢ ¬ψ} 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).