Recursively inseparable sets
In computability theory, two disjoint sets of natural numbers are called recursively inseparable if they cannot be "separated" with a recursive set.[1] These sets arise in the study of computability theory itself, particularly in relation to Π01 classes. Recursively 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). 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 recursive separating set, then the two sets are recursively inseparable.
Examples
If A is a non-recursive set then A and its complement are recursively inseparable. However, there are many examples of sets A and B that are disjoint, non-complementary, and recursively inseparable. Moreover, it is possible for A and B to be recursively inseparable, disjoint, and recursively 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 recursively 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 recursively inseparable. The inseparability of the sets of provable and refutable formulas holds for many other formal theories of arithmetic (Smullyan 1958).
References
- 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-4
- 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: 143–147, doi:10.1002/malq.19580040705, ISSN 0044-3050
 |
- ↑ Monk 1976, p. 100
