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
Definition and example
For the remainder of this article, assume that
A set A of natural numbers is called productive if there exists a total recursive (computable) function
A set A of natural numbers is called creative if A is recursively enumerable and its complement
The archetypal creative set is
To see this, we apply the definition of productivity function and show separately that
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
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:
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.
History
The seminal paper of Post (1944) defined the concept he called a Creative set. Reiterating, the set
"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