Computably inseparable

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  Π 1 0 {\displaystyle \Pi _{1}^{0}} classes. Computably inseparable sets also arise in the study of Gödel's incompleteness theorem.

## Definition

[edit]

The natural numbers are the set  N = { 0 , 1 , 2 , … } {\displaystyle \mathbb {N} =\\{0,1,2,\dots \\}} . Given disjoint subsets  A {\displaystyle A} and  B {\displaystyle B} of  N {\displaystyle \mathbb {N} } , a separating set C {\displaystyle C} is a subset of  N {\displaystyle \mathbb {N} } such that  A ⊆ C {\displaystyle A\subseteq C} and  B ∩ C = ∅ {\displaystyle B\cap C=\emptyset } (or equivalently,  A ⊆ C {\displaystyle A\subseteq C} and  B ⊆ C ′ {\displaystyle B\subseteq C'} , where  C ′ = N ∖ C {\displaystyle C'=\mathbb {N} \setminus C} denotes the complement of  C {\displaystyle C} ). For example,  A {\displaystyle A} itself is a separating set for the pair, as is  B ′ {\displaystyle B'} .

If a pair of disjoint sets  A {\displaystyle A} and  B {\displaystyle B} has no computable separating set, then the two sets are computably inseparable.

## Examples

[edit]

If  A {\displaystyle A} is a non-computable set, then  A {\displaystyle A} and its complement are computably inseparable. However, there are many examples of sets  A {\displaystyle A} and  B {\displaystyle B} that are disjoint, non-complementary, and computably inseparable. Moreover, it is possible for  A {\displaystyle A} and  B {\displaystyle B} to be computably inseparable, disjoint, and computably enumerable.

* Let  φ {\displaystyle \varphi } be the standard indexing of the partial computable functions. Then the sets  A = { e : φ e ( 0 ) = 0 } {\displaystyle A=\\{e:\varphi _{e}(0)=0\\}} and  B = { e : φ e ( 0 ) = 1 } {\displaystyle B=\\{e:\varphi _{e}(0)=1\\}} are computably inseparable (William Gasarch1998, p. 1047).
* Let  # {\displaystyle \\#} be a standard Gödel numbering for the formulas of Peano arithmetic. Then the set  A = { # ( ψ ) : P A ⊢ ψ } {\displaystyle A=\\{\\#(\psi ):PA\vdash \psi \\}} of provable formulas and the set  B = { # ( ψ ) : P A ⊢ ¬ ψ } {\displaystyle B=\\{\\#(\psi ):PA\vdash \lnot \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).

## 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 172077901+classes+in+computability+theory&rft.btitle=Handbook+of+computability+theory&rft.place=Amsterdam&rft.series=Stud.+Logic+Found.+Math.&rft.pages=37-85&rft.pub=North-Holland&rft.date=1999&rft_id=info:doi/10.1016/S0049-237X(99)80018-4&rft_id=https://mathscinet.ams.org/mathscinet-getitem?mr=1720779#id-name=MR&rft.aulast=Cenzer&rft.aufirst=Douglas&rfr_id=info:sid/en.wikipedia.org:Computably+inseparable" class="Z3988">
* 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 00992937–11&rft.pages=143-147&rft.date=1958&rft_id=https://mathscinet.ams.org/mathscinet-getitem?mr=0099293#id-name=MR&rft.issn=0044-3050&rft_id=info:doi/10.1002/malq.19580040705&rft.aulast=Smullyan&rft.aufirst=Raymond+M.&rfr_id=info:sid/en.wikipedia.org:Computably+inseparable" class="Z3988">