Jump to content

Computably inseparable

From Wikipedia, the free encyclopedia

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

[edit]

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

[edit]

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.

  • Let be the standard indexing of the partial computable functions. Then the sets and are computably inseparable (William Gasarch1998, p. 1047).
  • Let be a standard Gödel numbering 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

[edit]
  1. ^ Monk 1976, p. 100
  • Cenzer, Douglas (1999), "Π0
    1
    classes in computability theory", Handbook of computability theory, Stud. Logic Found. Math., vol. 140, Amsterdam: North-Holland, pp. 37–85, doi:10.1016/S0049-237X(99)80018-4, MR 1720779
  • Gasarch, William (1998), "A survey of recursive combinatorics", Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, Amsterdam: North-Holland, pp. 1041–1176, doi:10.1016/S0049-237X(98)80049-9, MR 1673598
  • Monk, J. Donald (1976), Mathematical Logic, Graduate Texts in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-0-387-90170-1
  • Smullyan, Raymond M. (1958), "Undecidability and recursive inseparability", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 4 (7–11): 143–147, doi:10.1002/malq.19580040705, ISSN 0044-3050, MR 0099293