# Computably inseparable

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Computably_inseparable
> Markdown URL: https://mediated.wiki/source/Computably_inseparable.md
> Source: https://en.wikipedia.org/wiki/Computably_inseparable
> Source revision: 1298641139
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Concept in computability theory

In [computability theory](/source/Computability_theory), two [disjoint sets](/source/Disjoint_sets) of natural numbers are called **computably inseparable** or **recursively inseparable** if they cannot be "separated" with a [computable set](/source/Computable_set).[1] These sets arise in the study of computability theory itself, particularly in relation to [Π 1 0 {\displaystyle \Pi _{1}^{0}} classes](/source/Pi01_class). Computably inseparable sets also arise in the study of [Gödel's incompleteness theorem](/source/G%C3%B6del's_incompleteness_theorem).

## Definition

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](/source/Complement_(set_theory)) of C {\displaystyle C} ). For example, A {\displaystyle A} itself is a [separating set](/source/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](/source/Computable_set) separating set, then the two sets are **computably inseparable**.

## Examples

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](/source/Computably_enumerable).

- Let φ {\displaystyle \varphi } be the standard indexing of the [partial computable functions](/source/Partial_computable_function). 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 Gasarch](/source/William_Gasarch)1998, p. 1047).

- Let # {\displaystyle \#} be a standard [Gödel numbering](/source/G%C3%B6del_numbering) for the formulas of [Peano arithmetic](/source/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

1. **[^](#cite_ref-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](/source/Doi_(identifier)):[10.1016/S0049-237X(99)80018-4](https://doi.org/10.1016%2FS0049-237X%2899%2980018-4), [MR](/source/MR_(identifier)) [1720779](https://mathscinet.ams.org/mathscinet-getitem?mr=1720779)

- [Gasarch, William](/source/William_Gasarch) (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](/source/Doi_(identifier)):[10.1016/S0049-237X(98)80049-9](https://doi.org/10.1016%2FS0049-237X%2898%2980049-9), [MR](/source/MR_(identifier)) [1673598](https://mathscinet.ams.org/mathscinet-getitem?mr=1673598)

- Monk, J. Donald (1976), [*Mathematical Logic*](https://archive.org/details/mathematicallogi00jdon), Graduate Texts in Mathematics, Berlin, New York: [Springer-Verlag](/source/Springer-Verlag), [ISBN](/source/ISBN_(identifier)) [978-0-387-90170-1](https://en.wikipedia.org/wiki/Special:BookSources/978-0-387-90170-1)

- [Smullyan, Raymond M.](/source/Raymond_M._Smullyan) (1958), "Undecidability and recursive inseparability", *Zeitschrift für Mathematische Logik und Grundlagen der Mathematik*, **4** (7–11): 143–147, [doi](/source/Doi_(identifier)):[10.1002/malq.19580040705](https://doi.org/10.1002%2Fmalq.19580040705), [ISSN](/source/ISSN_(identifier)) [0044-3050](https://search.worldcat.org/issn/0044-3050), [MR](/source/MR_(identifier)) [0099293](https://mathscinet.ams.org/mathscinet-getitem?mr=0099293)

---
Adapted from the Wikipedia article [Computably inseparable](https://en.wikipedia.org/wiki/Computably_inseparable) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Computably_inseparable?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.