Computablemente inseparables

En teoría de la computabilidad , dos conjuntos disjuntos de números naturales se denominan computablemente inseparables o recursivamente inseparables 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 las clases . Los conjuntos computablemente inseparables también surgen en el estudio del teorema de incompletitud de Gödel . $Estilo de visualización: Pi _{1}^{0}}$

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

Si un par de conjuntos disjuntos no tiene ningún conjunto separador computable , entonces los dos conjuntos son computablemente inseparables . ${\estilo de visualización A}$${\estilo de visualización B}$

Si es un conjunto no computable, entonces y su complemento son computablemente inseparables. Sin embargo, hay muchos ejemplos de conjuntos y que son disjuntos, no complementarios y computablemente inseparables. Además, es posible que y sean computablemente inseparables, disjuntos y computablemente enumerables . ${\estilo de visualización A}$${\estilo de visualización A}$${\estilo de visualización A}$${\estilo de visualización B}$${\estilo de visualización A}$${\estilo de visualización B}$

• Sea la indexación estándar de las funciones computables parciales . Entonces los conjuntos y son computacionalmente inseparables ( William Gasarch 1998, p. 1047).${\estilo de visualización \varphi}$${\displaystyle A=\{e:\varphi _ {e}(0)=0\}}$${\displaystyle B=\{e:\varphi _ {e}(0)=1\}}$
• Sea una numeración estándar de Gödel para las fórmulas de la aritmética de Peano . Entonces, el conjunto de fórmulas demostrables y el conjunto de fórmulas refutables son computablemente 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).${\estilo de visualización \#}$${\displaystyle A=\{\#(\psi ):PA\vdash \psi \}}$${\displaystyle B=\{\#(\psi ):PA\vdash \lnot \psi \}}$

• Cenzer, Douglas (1999), "Π⁰
  ₁Clases de teoría de la computabilidad", Manual de teoría de la computabilidad , Stud. Logic Found. Math., vol. 140, Ámsterdam: Holanda Septentrional, págs. 37-85, doi :10.1016/S0049-237X(99)80018-4, MR  1720779
• Gasarch, William (1998), "Un estudio de la combinatoria recursiva", Handbook of recursive mathematics, vol. 2 , Stud. Logic Found. Math., vol. 139, Ámsterdam: Holanda Septentrional, págs. 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