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.