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 Π0
1clases . Los conjuntos computablemente inseparables también surgen en el estudio del teorema de incompletitud de Gödel .
Definición
Los números naturales son el conjunto ω = {0, 1, 2, ...}. Dados los subconjuntos A y B disjuntos de ω, un conjunto de separación C es un subconjunto de ω tal que A ⊆ C y B ∩ C = ∅ (o equivalentemente, A ⊆ C y B ⊆ C ). Por ejemplo, A en sí es un conjunto de separación para el par, como es B .
Si un par de conjuntos disjuntos A y B no tiene un conjunto separador computable , entonces los dos conjuntos son inseparables computablemente .
Ejemplos de
Si A es un conjunto no computable, entonces A y su complemento son computablemente inseparables. Sin embargo, hay muchos ejemplos de conjuntos A y B que son inconexos, no complementarios y computablemente inseparables. Además, es posible que A y B sean computablemente inseparables, disjuntos y computablemente enumerables .
- Sea φ la indexación estándar de las funciones computables parciales . Entonces, los conjuntos A = { e : φ e (0) = 0 } y B = { e : φ e (0) = 1 } son computablemente inseparables ( William Gasarch 1998, p. 1047).
- Sea # una numeración estándar de Gödel para las fórmulas de la aritmética de Peano . Entonces, el conjunto A = {# (ψ): PA ⊢ ψ } de fórmulas demostrables y el conjunto B = {# (ψ): PA ⊢ ¬ψ } de fórmulas refutables son computablemente inseparables. La inseparabilidad de los conjuntos de fórmulas probables y refutables es válida para muchas otras teorías formales de la aritmética (Smullyan 1958).
Referencias
- ↑ Monk, 1976, p. 100
- Cenzer, Douglas (1999), "Π0
1clases de teoría de la computabilidad ", Manual de teoría de la computabilidad , Stud. Logic Found. Math., 140 , Amsterdam: North-Holland, 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 , Stud. Lógica encontrada. Math., 139 , Amsterdam: North-Holland, 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 : 143-147, doi : 10.1002 / malq.19580040705 , ISSN 0044-3050 , MR 0099293