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 aplicaciones importantes 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, suponga que es una numeración admisible de las funciones computables y W _i la numeración correspondiente de los conjuntos recursivamente enumerables .${\ estilo de visualización \ varphi _ {i}}$

Un conjunto A de números naturales se llama productivo si existe una función total recursiva (computable) tal que para todo , si entonces La función se llama función productiva para${\ estilo de visualización f}$${\displaystyle i\en \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 recursivamente enumerable 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 una función productiva y mostramos por separado que y :${\displaystyle i\in {\bar {K}}}$${\displaystyle i\not \in W_{i}}$

---