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
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 sense that a function is computable if there exists an algorithm that can do ...
s. Then the sets and are computably inseparable (
William Gasarch
William Ian Gasarch ( ; born 1959) is an American computer scientist known for his work in computational complexity theory, computability theory, computational learning theory, and Ramsey theory. He is currently a professor at the University of ...
1998, p. 1047).
* Let # be a standard
Gödel numbering
In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was developed by Kurt Gödel for the proof of his ...
for the formulas of
Peano arithmetic. Then the set of provable formulas and the set 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
*
*
*
* {{Citation , last1=Smullyan , first1=Raymond M. , author1-link=Raymond M. Smullyan , title=Undecidability and recursive inseparability , doi=10.1002/malq.19580040705 , mr=0099293 , year=1958 , journal=Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , issn=0044-3050 , volume=4 , pages=143–147
Computability theory