Computably inseparable

Short description: Concept in computability theory

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 Π01 classes. Computably inseparable sets also arise in the study of Gödel's incompleteness theorem.

## Definition

The natural numbers are the set ℕ={0,1,2,…}. 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⊆C′, where C′=ℕ∖C denotes the complement of C). For example, A itself is a separating set for the pair, as is B′.

If a pair of disjoint sets A and B has no computable 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 A={e:φe(0)=0} and B={e:φe(0)=1} are computably inseparable (William Gasarch1998, p. 1047).
* Let # be a standard Gödel numbering for the formulas of Peano arithmetic. Then the set A={#(ψ):PA⊢ψ} of provable formulas and the set B={#(ψ):PA⊢¬ψ} 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

1. ↑ Monk 1976, p. 100

* Cenzer, Douglas (1999), "Π01 classes in computability theory", Handbook of computability theory, Stud. Logic Found. Math., 140, Amsterdam: North-Holland, pp. 37–85, doi:10.1016/S0049-237X(99)80018-401+classes+in+computability+theory&rft.atitle=Handbook+of+computability+theory&rft.aulast=Cenzer&rft.aufirst=Douglas&rft.au=Cenzer, Douglas&rft.date=1999&rft.series=Stud.+Logic+Found.+Math.&rft.volume=140&rft.pages=pp. 37–85&rft.place=Amsterdam&rft.pub=North-Holland&rft_id=info:doi/10.1016/S0049-237X(99)80018-4&rfr_id=info:sid/en.wikibooks.org:Computably_inseparable">
* Gasarch, William (1998), "A survey of recursive combinatorics", Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., 139, Amsterdam: North-Holland, pp. 1041–1176, doi:10.1016/S0049-237X(98)80049-9
* Monk, J. Donald (1976), Mathematical Logic, Graduate Texts in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-0-387-90170-1, https://archive.org/details/mathematicallogi00jdon
* 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

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Computably inseparable. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Computably_inseparable&oldid=324843"