Concepto en la teoría de la computabilidad.
En la 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}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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, él mismo es un conjunto separador para el par, como lo es .![{\displaystyle \mathbb {N} =\{0,1,2,\dots \}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle C}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \mathbb {N}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A\subseteq C}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B\cap C=\emptyset}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A\subseteq C}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B\subseteq C'}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle C'=\mathbb {N} \setminus C}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle C}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B'}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Si un par de conjuntos disjuntos y no tiene un conjunto separador computable , entonces los dos conjuntos son computablemente inseparables .![{\displaystyle A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Ejemplos
Si es un conjunto no computable, entonces y su complemento son computablemente inseparables. Sin embargo, hay muchos ejemplos de conjuntos que son disjuntos, no complementarios y computablemente inseparables. Además, es posible que y ser computablemente inseparable, disjunto y computablemente enumerable . ![{\displaystyle A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- Sea la indexación estándar de las funciones computables parciales . Entonces los conjuntos y son computablemente inseparables ( William Gasarch 1998, p. 1047).
![{\displaystyle \varphi}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A=\{e:\varphi _ {e}(0)=0\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B=\{e:\varphi _ {e}(0)=1\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- 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 es válida para muchas otras teorías formales de la aritmética (Smullyan 1958).
![{\displaystyle\#}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle A=\{\#(\psi ):PA\vdash \psi \}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B=\{\#(\psi ):PA\vdash \lnot \psi \}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Referencias
- Cenzer, Douglas (1999), "Π0
1clases de teoría de computabilidad", Manual de teoría de 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 combinatoria recursiva", Manual de matemáticas recursivas, vol. 2 , Semental. Lógica encontrada. Matemáticas, vol. 139, Ámsterdam: Holanda Septentrional, págs. 1041–1176, doi :10.1016/S0049-237X(98)80049-9, SEÑOR 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