Ensembles récursivement inséparables
# Ensembles récursivement inséparables

En théorie de la calculabilité, deux ensembles disjoints d'entiers naturels sont appelés récursivement inséparables s'ils ne peuvent pas être "séparés" par un ensemble $récursif^,^,.$

## Définition

Les entiers naturels sont l'ensemble $\mathbb {N} =\{0,1,2,\dots \}$. Étant donné deux sous-ensembles disjoints A et B de $\mathbb {N}$, un ensemble séparateur C est un sous-ensemble de $\mathbb {N}$ tel que A ⊆ C et B ∩ C = ∅ (ou de manière équivalente, A ⊆ C et B ⊆ C). Par exemple, A lui-même est un ensemble séparateur pour la paire, tout comme B.

Si une paire d'ensembles disjoints A et B n'a pas d'ensemble séparateur récursif, alors les deux ensembles sont récursivement inséparables.

## Exemples

Si A est un ensemble non récursif, alors A et son complément sont récursivement inséparables (dont l'un des deux n'est pas récursivement énumérable). Cependant, il existe de nombreux exemples d'ensembles A et B qui sont disjoints, non complémentaires, et récursivement inséparables. De plus, il est possible que A et B soient récursivement inséparables, disjoints et tous deux récursivement énumérable.

* Soit φ une énumération standard des fonctions partielles calculables. Alors les ensembles A = {e : $φ_e(0)$ = 0 et B = {e : $φ_e(0)$ = 1 sont récursivement inséparables. Par l'absurde, s'il existe un séparateur récursif C, alors on peut construire le programme qui commence par calculer si son propre index dans l'énumération est dans C ou C, puis donne respectivement 1 ou 0 en sortie. Dans les deux cas cela contredit son appartenance à B ou A (respectivement).
* Soit # un codage de Gödel standard pour les formules de l'arithmétique de Peano. Alors l'ensemble A = { #(ψ) : PA ⊢ ψ } des formules prouvables et l'ensemble B = { #(ψ) : PA ⊢ ¬ψ } des formules réfutables sont récursivement inséparables. L'inséparabilité des ensembles de formules prouvables et réfutables vaut pour de nombreuses autres théories formelles de l'arithmétique.
