Conjuntos creativos y productivos

En la teoría de la computabilidad , los conjuntos productivos y los conjuntos creativos son tipos de conjuntos de números naturales que tienen importantes aplicaciones en la 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).

Para el resto de este artículo, supongamos que es una numeración admisible de las funciones computables y W _i la numeración correspondiente de los conjuntos enumerables recursivamente . ${\displaystyle \varphi _{i}}$

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

Un conjunto A de números naturales se denomina creativo si A es recursivamente enumerable y su complemento es productivo. Sin embargo, no todo conjunto productivo tiene 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\no \en W_{i}}$

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

Ningún conjunto productivo A puede ser recursivamente enumerable, 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 dicho 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 que es inyectiva y total .

Los siguientes teoremas, debidos a Myhill (1955), muestran que en cierto sentido todos los conjuntos creativos son similares y todos los conjuntos productivos son similares . ^[1]${\estilo de visualización 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 recursivamente isomorfo a K , es decir, existe una biyección computable total f en los números naturales tal que f ( C ) = K .

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 sea un conjunto recursivamente enumerable de oraciones verdaderas, hay al menos una oración verdadera que no está en W. Esto se puede usar 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 lo tanto, T es un ejemplo de un conjunto productivo cuyo complemento no es creativo.

El artículo seminal de Post (1944) definió el concepto que llamó un 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 suma 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 decir "Soy indemostrable en esta teoría axiomática". Sin embargo, la prueba de Gödel no funcionó a partir del concepto de oraciones verdaderas, y en su lugar utilizó el concepto de una teoría consistente, lo que condujo al segundo teorema de incompletitud . Después de que Post completó su versión de incompletitud, agregó lo siguiente: ${\estilo de visualización K}$${\displaystyle d(x)=[[x]](x)+1}$

"La conclusión ineludible es que incluso para un cuerpo de proposiciones matemáticas tan fijo y bien definido, el pensamiento matemático es, y debe seguir siendo, esencialmente creativo". ^[2]

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 modo 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 está dada por para todos donde codifica las instrucciones para . Usando la notación anterior , y la función diagonal surge de manera 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. ${\estilo de visualización K}$${\estilo de visualización d(x)}$${\estilo de visualización \Phi}$${\estilo de visualización \Phi}$${\displaystyle \Phi(w,x)=}$ ${\estilo de visualización w}$ ${\estilo de visualización x}$${\estilo de visualización f}$${\displaystyle f(x)=\Phi(e,x)}$${\estilo de visualización x}$${\estilo de visualización e}$${\estilo de visualización 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 posibles contraejemplos a la conjetura de Berman-Hartmanis sobre el isomorfismo de conjuntos NP-completos .

• Davis, Martin (1958), Computabilidad e insolubilidad , 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: una introducción a la teoría de la recursión , Academic Press, ISBN 978-0-12-384958-8.
• Joseph, Deborah ; Young, Paul (1985), "Algunas observaciones sobre funciones testigo para conjuntos no polinómicos 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, Sr.  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, SEÑOR  0071379.
• Post, Emil L. (1944), "Conjuntos enumerables recursivamente 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 (2.ª ed.), Cambridge, MA: MIT Press, ISBN 0-262-68052-1, Sr.  0886890.
• Soare, Robert I. (1987), Conjuntos y grados enumerables recursivamente: un estudio de funciones computables y conjuntos generados computacionalmente , Perspectivas en lógica matemática, Berlín: Springer-Verlag, ISBN 3-540-15299-7, Sr.  0882921.