Computably inseparable explained
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.[1] 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
and
of
, a
separating set
is a subset of
such that
and
(or equivalently,
and
, where
denotes the
complement of
). For example,
itself is a separating set for the pair, as is
.
If a pair of disjoint sets
and
has no
computable separating set, then the two sets are
computably inseparable.
Examples
If
is a non-computable set, then
and its complement are computably inseparable. However, there are many examples of sets
and
that are disjoint, non-complementary, and computably inseparable. Moreover, it is possible for
and
to be computably inseparable, disjoint, and
computably enumerable.
be the standard indexing of the
partial computable functions. Then the sets
and
are computably inseparable (
William Gasarch1998, p. 1047).
be a standard
Gödel numbering for the formulas of
Peano arithmetic. Then the set
A=\{\#(\psi):PA\vdash\psi\}
of provable formulas and the set
B=\{\#(\psi):PA\vdashlnot\psi\}
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).
Notes and References
- Monk 1976, p. 100
