In computability theory, productive sets and creative sets are types of sets of natural numbers that have important applications in mathematical logic. They are a standard topic in mathematical logic textbooks such as and .
For the remainder of this article, assume that
\varphii
A set A of natural numbers is called productive if there exists a total recursive (computable) function
f
i\inN
Wi\subseteqA
f(i)\inA\setminusWi.
f
A.
A set A of natural numbers is called creative if A is recursively enumerable and its complement
N\setminusA
The archetypal creative set is
K=\{i\midi\inWi\}
\bar{K}=\{i\midi\not\inWi\}
To see this, we apply the definition of a productive function and show separately that
i\in\bar{K}
i\not\inWi
i\in\bar{K}
i\inK
i\inWi
Wi\subseteq\bar{K}
i\in\bar{K}
i\in\bar{K}
i\not\inWi
i\inWi
i\inK
i\not\inWi
No productive set A can be recursively enumerable, because whenever A contains every number in an r.e. set Wi it contains other numbers, and moreover there is an effective procedure to produce an example of such a number from the index i. Similarly, no creative set can be decidable, because this would imply that its complement, a productive set, is recursively enumerable.
Any productive set has a productive function that is injective and total.
The following theorems, due to Myhill (1955), show that in a sense all creative sets are like
K
\bar{K}
Theorem. Let P be a set of natural numbers. The following are equivalent:
\bar{K}
\bar{K}
Theorem. Let C be a set of natural numbers. The following are equivalent:
The set of all provable sentences in an effective axiomatic system is always a recursively enumerable set. If the system is suitably complex, like first-order arithmetic, then the set T of Gödel numbers of true sentences in the system will be a productive set, which means that whenever W is a recursively enumerable set of true sentences, there is at least one true sentence that is not in W. This can be used to give a rigorous proof of Gödel's first incompleteness theorem, because no recursively enumerable set is productive. The complement of the set T will not be recursively enumerable, and thus T is an example of a productive set whose complement is not creative.
The seminal paper of defined the concept he called a Creative set. Reiterating, the set
K
d(x)=[[x]](x)+1
"The conclusion is unescapable that even for such a fixed, well defined body of mathematical propositions, mathematical thinking is, and must remain, essentially creative."
The usual creative set
K
d(x)
\Phi
\Phi
\Phi(w,x)=
w
x
f
f(x)=\Phi(e,x)
x
e
f
\Phi(e,x)=[[e]](x)
d(x)=[[x]](x)+1
formulated an analogous concept, polynomial creativity, in computational complexity theory, and used it to provide potential counterexamples to the Berman–Hartmanis conjecture on isomorphism of NP-complete sets.