Inseparables computacionalmente

En la teoría de la computabilidad , dos conjuntos disjuntos de números naturales se denominan inseparables computacionalmente o inseparables recursivamente si no pueden "separarse" con un conjunto computable . ^{[ 1 ]} Estos conjuntos surgen en el estudio de la propia teoría de la computabilidad, particularmente en relación con${\displaystyle \Pi _{1}^{0}}$clases . Los conjuntos computacionalmente inseparables también surgen en el estudio del teorema de incompletitud de Gödel .

Los números naturales son el conjunto${\displaystyle \mathbb {N} =\{0,1,2,\dots \}}$. Dados subconjuntos disjuntos${\displaystyle A}$y${\displaystyle B}$de${\displaystyle \mathbb {N} }$, un conjunto separador${\displaystyle C}$es un subconjunto de${\displaystyle \mathbb {N} }$de tal manera que ${\displaystyle A\subsetequ C}$y${\displaystyle B\cap C=\emptyset }$(o equivalentemente, ${\displaystyle A\subsetequ C}$y${\displaystyle B\subsetequ C'}$, dónde${\displaystyle C'=\mathbb {N} \setminus C}$denota el complemento de${\displaystyle C}$). Por ejemplo,${\displaystyle A}$en sí mismo es un conjunto separador para el par, como lo es${\displaystyle B'}$.

Si un par de conjuntos disjuntos${\displaystyle A}$y${\displaystyle B}$Si no tiene un conjunto separador computable , entonces los dos conjuntos son computacionalmente inseparables .

Si${\displaystyle A}$es un conjunto no computable, entonces${\displaystyle A}$y su complemento son computacionalmente inseparables. Sin embargo, hay muchos ejemplos de conjuntos${\displaystyle A}$y${\displaystyle B}$que son disjuntos, no complementarios y computacionalmente inseparables. Además, es posible que${\displaystyle A}$y${\displaystyle B}$ser computacionalmente inseparables, disjuntos y computacionalmente enumerables .

• Dejar${\displaystyle \varphi }$sea ​​la indexación estándar de las funciones computables parciales . Entonces los conjuntos${\displaystyle A=\{e:\varphi _ {e}(0)=0\}}$y${\displaystyle B=\{e:\varphi _ {e}(0)=1\}}$son computacionalmente inseparables ( William Gasarch 1998, p.  1047).
• Dejar${\displaystyle \#}$sea ​​una numeración estándar de Gödel para las fórmulas de la aritmética de Peano . Entonces el conjunto${\displaystyle A=\{\#(\psi ):PA\vdash \psi \}}$de fórmulas demostrables y el conjunto${\displaystyle B=\{\#(\psi ):PA\vdash \lnot \psi \}}$Las fórmulas refutables son computacionalmente inseparables. La inseparabilidad de los conjuntos de fórmulas demostrables y refutables se cumple para muchas otras teorías formales de la aritmética (Smullyan 1958).

• Cenzer, Douglas (1999), "Clases Π ⁰ ₁ en la teoría de la computabilidad", Manual de teoría de la computabilidad , Stud. Logic Found. Math., vol.  140, Ámsterdam: North-Holland, pp. 37–85 , doi : 10.1016/S0049-237X(99)80018-4 , MR 1720779  
• Gasarch, William (1998), "Un estudio de la combinatoria recursiva", Manual de matemáticas recursivas, vol. 2 , Stud. Logic Found. Math., vol.  139, Ámsterdam: North-Holland, pp. 1041–1176 , doi : 10.1016/S0049-237X(98)80049-9 , MR 1673598  
• Monk, J. Donald (1976), Lógica matemática , Textos de posgrado en matemáticas, Berlín, Nueva York: Springer-Verlag , ISBN 978-0-387-90170-1
• Smullyan, Raymond M. (1958), "Indecidibilidad e inseparabilidad recursiva", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 4 ( 7– 11): 143– 147, doi : 10.1002/malq.19580040705 , ISSN 0044-3050 , Señor 0099293