En la teoría de la computabilidad , los conjuntos productivos y los conjuntos creativos son tipos de conjuntos de números naturales que tienen aplicaciones importantes en lógica matemática . Son un tema estándar en los libros de texto de lógica matemática como Soare (1987) y Rogers (1987) .
Definición y ejemplo
Para el resto de este artículo, suponga que es una numeración admisible de las funciones computables y W i la numeración correspondiente de los conjuntos enumerables recursivamente .
Un conjunto A de números naturales se llama productivo si existe una función total recursiva (computable) para que para todos , Si luego La función se llama función productiva para
Un conjunto A de números naturales se llama creativo si A es enumerable recursivamente y su complementoes productivo. Sin embargo, no todos los conjuntos productivos tienen un complemento recursivamente enumerable, como se ilustra a continuación.
El conjunto creativo arquetípico es , el conjunto que representa el problema de la detención . Su complementoes productivo con función productiva f ( i ) = i (la función identidad).
Para ver esto, aplicamos la definición de función de productividad y mostramos por separado que y :
- : suponga , luego , ahora dado que tenemos , Esto conduce a una contradicción. Entonces.
- : de hecho si , entonces seria cierto que , pero hemos demostrado lo contrario en el punto anterior. Entonces.
Propiedades
Ningún conjunto productivo A puede ser enumerable de forma recursiva, porque siempre que A contiene todos los números de un conjunto W i , contiene otros números y, además, existe un procedimiento eficaz para producir un ejemplo de tal número a partir del índice i . De manera similar, ningún conjunto creativo puede ser decidible , porque esto implicaría que su complemento, un conjunto productivo, es recursivamente enumerable.
Todo conjunto productivo tiene una función productiva inyectiva y total .
Los siguientes teoremas, debidos a Myhill (1955), muestran que, en cierto sentido, todos los conjuntos creativos son como y todos los conjuntos productivos son como . [1]
Teorema. Sea P un conjunto de números naturales. Los siguientes son equivalentes:
- P es productivo.
- es 1-reducible a P .
- es m-reducible a P .
Teorema. Sea C un conjunto de números naturales. Los siguientes son equivalentes:
- C es creativo.
- C es 1 completo
- C es de forma recursiva isomorfo a K , es decir, hay un total computable biyección f en los números naturales tal que f ( C ) = K .
Aplicaciones en lógica matemática
El conjunto de todas las oraciones demostrables en un sistema axiomático efectivo es siempre un conjunto recursivamente enumerable . Si el sistema es adecuadamente complejo, como la aritmética de primer orden , entonces el conjunto T de números de Gödel de oraciones verdaderas en el sistema será un conjunto productivo, lo que significa que siempre que W es un conjunto recursivamente enumerable de oraciones verdaderas, hay al menos una verdadera pena que no está en W . Esto puede usarse para dar una prueba rigurosa del primer teorema de incompletitud de Gödel , porque ningún conjunto recursivamente enumerable es productivo. El complemento del conjunto T no será recursivamente enumerable y, por tanto, T es un ejemplo de un conjunto productivo cuyo complemento no es creativo.
Historia
El artículo fundamental de Post (1944) definió el concepto que denominó Conjunto creativo. Reiterando, el conjunto mencionado anteriormente y definido como el dominio de la función que toma la diagonal de todas las funciones parciales computables de 1 lugar enumeradas y les agrega 1 es un ejemplo de un conjunto creativo. [2] Post dio una versión del Teorema de incompletitud de Gödel usando sus conjuntos creativos, donde originalmente Gödel había construido en cierto sentido una oración que podría traducirse libremente como diciendo "No soy demostrable en esta teoría axiomática". Sin embargo, la demostración de Gödel no funcionó a partir del concepto de oraciones verdaderas, sino que utilizó el concepto de una teoría consistente, lo que llevó al segundo teorema de incompletitud . Después de que Post completó su versión de incompletitud, agregó lo siguiente:
"La conclusión es ineludible de que incluso para un cuerpo tan fijo y bien definido de proposiciones matemáticas, el pensamiento matemático es, y debe seguir siendo, esencialmente creativo". [2]
El conjunto creativo habitual definido usando la función diagonal tiene su propio desarrollo histórico. Alan Turing en un artículo de 1936 sobre la máquina de Turing mostró la existencia de una computadora universal que calcula lafunción. La función se define de tal manera que ( el resultado de aplicar las instrucciones codificadas por a la entrada ), y es universal en el sentido de que cualquier función parcial calculable es dado por para todos dónde codifica las instrucciones para . Usando la notación anterior, y la función diagonal surge de forma bastante natural como . En última instancia, estas ideas están conectadas con la tesis de Church que dice que la noción matemática de funciones parciales computables es la formalización correcta de una función parcial efectivamente calculable, que no se puede probar ni refutar. Church usó el cálculo Lambda , Turing una computadora idealizada y más tarde Emil Post en su enfoque, todos los cuales son equivalentes.
Deborah Joseph y Paul Young ( 1985 ) formularon un concepto análogo, la creatividad polinomial , en la teoría de la complejidad computacional , y lo utilizaron para proporcionar contraejemplos potenciales a la conjetura de Berman-Hartmanis sobre el isomorfismo de conjuntos completos NP .
Notas
- ^ Soare (1987) ; Rogers (1987) .
- ↑ a b Enderton (2010) , págs.79 , 80, 120.
Referencias
- Davis, Martin (1958), Computability and Inexolvability , Series in Information Processing and Computers, Nueva York: McGraw-Hill, MR 0124208 CS1 maint: parámetro desalentado ( enlace ). Reimpreso en 1982 por Dover Publications.
- Enderton, Herbert B. (2010), Teoría de la computabilidad: una introducción a la teoría de la recursividad , Academic Press, ISBN 978-0-12-384958-8.
- José, Deborah ; Young, Paul (1985), "Algunas observaciones sobre las funciones de testigos para conjuntos no polinomiales y no completos en NP" , Theoretical Computer Science , 39 (2-3): 225-237, doi : 10.1016 / 0304-3975 (85) 90140-9 , MR 0821203
- Kleene, Stephen Cole (2002), lógica matemática , Mineola, NY: Dover Publications Inc., ISBN 0-486-42533-9, Señor 1950307 CS1 maint: parámetro desalentado ( enlace ). Reimpresión del original de 1967, Wiley, MR0216930 .
- Myhill, John (1955), "Conjuntos creativos", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 1 (2): 97–108, doi : 10.1002 / malq.19550010205 , MR 0071379 CS1 maint: parámetro desalentado ( enlace ).
- Post, Emil L. (1944), "Conjuntos recursivamente enumerables de números enteros positivos y sus problemas de decisión", Boletín de la American Mathematical Society , 50 (5): 284–316, doi : 10.1090 / S0002-9904-1944-08111- 1 , MR 0010514 CS1 maint: parámetro desalentado ( enlace )
- Rogers, Hartley, Jr. (1987), Teoría de funciones recursivas y computabilidad efectiva (2a ed.), Cambridge, MA: MIT Press, ISBN 0-262-68052-1, MR 0886890.
- Soare, Robert I. (1987), Conjuntos y grados recursivamente enumerables: un estudio de funciones computables y conjuntos generados computablemente , Perspectivas en lógica matemática, Berlín: Springer-Verlag, ISBN 3-540-15299-7, MR 0882921.