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écursifModèle:,Modèle:,.

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 ⊆ Modèle:Surligner). Par exemple, A lui-même est un ensemble séparateur pour la paire, tout comme Modèle:Surligner.

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 Modèle:Nobr et Modèle:Nobr 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 Modèle:Surligner, 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 Modèle:Nobr } des formules prouvables et l'ensemble Modèle:Nobr } 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.