Creative and productive sets

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 Soare (1987) and Rogers (1987).

Definition and example

For the remainder of this article, assume that φ_i is an acceptable numbering of the computable functions and W_i the corresponding numbering of the recursively enumerable sets.

A set A of natural numbers is called productive if there exists a partial computable function f so that for all $i \in \mathbb{N}$, if $W_i \subseteq A$ then $f(i) \in A \setminus W_i.$ The function f is called the productive function for A.

A set A of natural numbers is called creative if A is recursively enumerable and its complement $\mathbb{N}\setminus A$ is productive. Not every productive set has a recursively enumerable complement, however, as illustrated below.

The archetypal creative set is $K = \{ i \mid i \in W_i \}$, the set representing the halting problem. Its complement $\bar{K} = \{ i \mid i \not \in W_i \}$ is productive with productive function f(i) = i. To see this, assume $W_i \subseteq \bar{K}$. If i were in W_i then $i \in K$ and thus $i \not \in \bar{K}$. This would mean $W_i \not \subseteq \bar{K}$, so we can conclude $i \not \in W_i$, which means $i \in \bar{K}$.

Properties

No productive set A can be recursively enumerable, because whenever A contains every number in an r.e. set W_i 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 and all productive sets are like $\bar{K}$ (see Soare (1987) and Rogers (1987)).

Theorem. Let P be a set of natural numbers. The following are equivalent:

• P is productive.
• $\bar{K}$ is 1-reducible to P.
• $\bar{K}$ is m-reducible to P.

Theorem. Let C be a set of natural numbers. The following are equivalent:

• C is creative.
• C is 1-complete
• C is recursively isomorphic to K, that is, there is a total computable bijection f on the natural numbers such that f(C) = K.

Applications in mathematical logic

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.

References

• Davis, M., 1982. Computability and Unsolvability. New York: Dover.
• Kleene, S. C.,2002. Mathematical Logic. New York: Dover.
• Myhill, J., 1955. "Creative sets," Z. Math. Logik Grundlag. Math., v. 1, pp. 97–108.
• Rogers, H., 1987. Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press.
• Soare, R., 1987. Recursively Enumerable Sets and Degrees. Berlin: Springer.