Conjuntos creativos y productivos - Creative and productive sets

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 recursivamente enumerables . ${\ Displaystyle \ varphi _ {i}}$

Un conjunto A de números naturales se llama productivo si existe una función total recursiva (computable) de modo que para todos , si entonces La función se llama función productiva para ${\ Displaystyle f}$${\ Displaystyle i \ in \ mathbb {N}}$${\ Displaystyle W_ {i} \ subseteq A}$${\ Displaystyle f (i) \ in A \ setminus W_ {i}.}$${\ Displaystyle f}$${\ Displaystyle A.}$

Un conjunto A de números naturales se llama creativo si A es enumerable recursivamente y su complemento es productivo. Sin embargo, no todos los conjuntos productivos tienen un complemento recursivamente enumerable, como se ilustra a continuación. ${\ Displaystyle \ mathbb {N} \ setminus A}$

El conjunto creativo arquetípico es el conjunto que representa el problema de la detención . Su complemento es productivo con función productiva f ( i ) = i (la función identidad). ${\ Displaystyle K = \ {i \ mid i \ in W_ {i} \}}$${\ Displaystyle {\ bar {K}} = \ {i \ mid i \ not \ in W_ {i} \}}$

Para ver esto, aplicamos la definición de función productiva y mostramos por separado que y : ${\ Displaystyle i \ in {\ bar {K}}}$${\ Displaystyle i \ not \ in W_ {i}}$

• ${\ Displaystyle i \ in {\ bar {K}}}$ Supongamos , entonces , que ahora que tenemos , esto conduce a una contradicción. Entonces . ${\ Displaystyle i \ in K}$${\ Displaystyle i \ in W_ {i}}$${\ Displaystyle W_ {i} \ subseteq {\ bar {K}}}$${\ Displaystyle i \ in {\ bar {K}}}$${\ Displaystyle i \ in {\ bar {K}}}$
• ${\ Displaystyle i \ not \ in W_ {i}}$ : de hecho si , entonces sería cierto que , pero hemos demostrado lo contrario en el punto anterior. Entonces . ${\ Displaystyle i \ in W_ {i}}$${\ Displaystyle i \ in K}$${\ Displaystyle i \ not \ in W_ {i}}$

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 semejantes y todos los conjuntos productivos son semejantes . ${\ Displaystyle K}$${\ Displaystyle {\ bar {K}}}$

Teorema. Sea P un conjunto de números naturales. Los siguientes son equivalentes:

• P es productivo.
• ${\ Displaystyle {\ bar {K}}}$ es 1-reducible a P .
• ${\ Displaystyle {\ bar {K}}}$ 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. 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: ${\ Displaystyle K}$${\ Displaystyle d (x) = [[x]] (x) +1}$

"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".

El conjunto creativo habitual definido mediante 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 la funció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 viene dada por para todos donde codifica las instrucciones para . Usando la notación anterior , 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 puede ser probada ni refutada. Church usó el cálculo lambda , Turing una computadora idealizada y más tarde Emil Post en su enfoque, todos los cuales son equivalentes. ${\ Displaystyle K}$${\ Displaystyle d (x)}$${\ Displaystyle \ Phi}$${\ Displaystyle \ Phi}$${\ Displaystyle \ Phi (w, x) =}$ ${\ Displaystyle w}$ ${\ Displaystyle x}$${\ Displaystyle f}$${\ Displaystyle f (x) = \ Phi (e, x)}$${\ Displaystyle x}$${\ Displaystyle e}$${\ Displaystyle f}$${\ Displaystyle \ Phi (e, x) = [[e]] (x)}$${\ Displaystyle d (x) = [[x]] (x) +1}$

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

Referencias

• Davis, Martin (1958), Computability and Inexolvability , Series in Information Processing and Computers, Nueva York: McGraw-Hill, MR   0124208 . Reimpreso en 1982 por Dover Publications.
• Enderton, Herbert B. (2010), Teoría de la computabilidad: 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 . Reimpresión del original de 1967, Wiley, MR 0216930 .
• 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 .
• 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
• 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 enumerables recursivamente: 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 .