In
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ...
, two disjoint sets of natural numbers are called computably inseparable or recursively inseparable if they cannot be "separated" with a
computable set
In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly ...
.
[Monk 1976, p. 100] These sets arise in the study of computability theory itself, particularly in relation to
Π classes. Computably inseparable sets also arise in the study of
Gödel's incompleteness theorem.
Definition
The natural numbers are the set
. 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'' ⊆ ). For example, ''A'' itself is a separating set for the pair, as is '.
If a pair of disjoint sets ''A'' and ''B'' has no
computable
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...
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
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
.
* Let φ be the standard indexing of the
partial computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the