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 e ...
, two disjoint sets of natural numbers are called computably inseparable or recursively inseparable if they 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. 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.
* Let φ be the standard indexing of the
partial computable functions. 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
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
. 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