Conjuntos creativos y productivos

En la teoría de la computabilidad , los conjuntos productivos y creativos son tipos de conjuntos de números naturales que tienen aplicaciones importantes en la lógica matemática . Son un tema estándar en libros de texto de lógica matemática como los de Soare (1987) y Rogers (1987) .

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

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

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

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

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

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

Ningún conjunto productivo A puede ser recursivamente enumerable, porque siempre que A contiene todos los números de un reconjunto W _i también contiene otros números, y además existe un procedimiento efectivo 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 como${\displaystyle K}$y todos los conjuntos productivos son como${\displaystyle {\bar {K}}}$. ^{[ 1 ]}

Teorema. Sea P un conjunto de números naturales. Las siguientes proposiciones 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. Las siguientes proposiciones 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 sentencias demostrables en un sistema axiomático efectivo es siempre un conjunto recursivamente enumerable . Si el sistema es suficientemente complejo, como la aritmética de primer orden , entonces el conjunto T de números de Gödel de sentencias verdaderas en el sistema será un conjunto productivo, lo que significa que siempre que W sea un conjunto recursivamente enumerable de sentencias verdaderas, existe al menos una sentencia verdadera que no está en W. Esto puede usarse para dar una demostración 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 fundamental de Post (1944) definió el concepto que él llamó conjunto creativo. Reiterando, el conjunto${\displaystyle K}$mencionado anteriormente y definido como el dominio de la función${\displaystyle d(x)=[[x]](x)+1}$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 podía traducirse libremente como decir "Soy indemostrable en esta teoría axiomática". Sin embargo, la demostración de Gödel no funcionaba desde el concepto de oraciones verdaderas, sino que usaba 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, luego agregó lo siguiente:

"La conclusión es ineludible: incluso para un conjunto 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${\displaystyle K}$definido mediante la función diagonal${\displaystyle d(x)}$tiene su propio desarrollo histórico. Alan Turing en un artículo de 1936 sobre la máquina de Turing demostró la existencia de una computadora universal que calcula la${\displaystyle \Phi }$función. La función${\displaystyle \Phi }$se define de tal manera que ${\displaystyle \Phi (w,x)=}$( el resultado de aplicar las instrucciones codificadas por${\displaystyle w}$a la entrada${\displaystyle x}$), y es universal en el sentido de que cualquier función parcial calculable${\displaystyle f}$es dado por${\displaystyle f(x)=\Phi (e,x)}$a pesar de${\displaystyle x}$dónde${\displaystyle e}$codifica las instrucciones para${\displaystyle f}$. Utilizando la notación anterior ${\displaystyle \Phi (e,x)=[[e]](x)}$y la función diagonal surge de forma bastante natural como${\displaystyle d(x)=[[x]](x)+1}$En última instancia, estas ideas están relacionadas con la tesis de Church , que afirma que la noción matemática de funciones parciales computables es la formalización correcta de una función parcial efectivamente calculable, la cual no puede ser probada ni refutada. Church utilizó el cálculo lambda , Turing (una computadora idealizada) y, posteriormente, Emil Post en su enfoque; todos ellos son equivalentes.

Deborah Joseph y Paul Young ( 1985 ) formularon un concepto análogo, 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 irresolubilidad , Serie en Procesamiento de la Información y Computadoras, 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 las funciones testigo 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, MR 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 recursivamente enumerables de enteros positivos y sus problemas de decisión", Bulletin of the American Mathematical Society , 50 (5): 284–316 , doi : 10.1090/S0002-9904-1944-08111-1 , MR 0010514 
• Rogers, Hartley Jr. (1987), Teoría de las funciones recursivas y la computabilidad efectiva (2.ª  ed.), Cambridge, MA: MIT Press, ISBN 0-262-68052-1, SR 0886890 .
• Soare, Robert I. (1987), Conjuntos y grados recursivamente enumerables: Un estudio de funciones computables y conjuntos generados computacionalmente , Perspectivas en lógica matemática, Berlín: Springer-Verlag, ISBN 3-540-15299-7, MR 0882921 .