Computablemente inseparables

Concepto en la teoría de la computabilidad

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 . ${\displaystyle \Pi _{1}^{0}}$

Definición

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,\dots \}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle C}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle A\subseteq C}$ ${\displaystyle B\cap C=\emptyset }$ ${\displaystyle A\subseteq C}$ ${\displaystyle B\subseteq C'}$ ${\displaystyle C'=\mathbb {N} \setminus C}$ ${\displaystyle C}$ ${\displaystyle A}$ ${\displaystyle B'}$

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

Ejemplos

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 . ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

• Sea la indexación estándar de las funciones computables parciales . Entonces los conjuntos y son computacionalmente inseparables ( William Gasarch 1998, p. 1047). ${\displaystyle \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). ${\displaystyle \#}$ ${\displaystyle A=\{\#(\psi ):PA\vdash \psi \}}$ ${\displaystyle B=\{\#(\psi ):PA\vdash \lnot \psi \}}$

Referencias

1. Monje 1976, pág. 100

• 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