Creative and productive sets

From Wikipedia, the free encyclopedia

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).

Contents

[edit] Definition and example

For the remainder of this article, assume that \varphi_i is an acceptable numbering of the computable functions and Wi 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 Wi 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}.

[edit] Properties

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 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:

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

[edit] 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.

[edit] 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.