Creative and productive sets

From Wikipedia, the free encyclopedia
  (Redirected from Creative set)
Jump to: navigation, search

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

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 total recursive (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 (the identity function).

To see this, we apply the definition of productivity function and show separately that i \in \bar{K} and i \not \in W_i

  • i \in \bar{K}: suppose i \in K, then i \in W_i, now given that W_i \in \bar{K} we have i \in \bar{K}, this leads to a contraddiction so i \in \bar{K}.
  • i \not \in W_i: in fact if i \in W_i then would be true that i \in K but we have demonstrated the contrary in the previous point. So i \not \in W_i.

Properties[edit]

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}.[1]

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

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

The seminal paper of Post (1944) defined the concept he called a Creative set. Reiterating, the set  K referenced above and defined as the domain of the function d(x)=[[x]](x)+1 that takes the diagonal of all enumerated 1-place computable partial functions and adds 1 to them is an example of a creative set.[2] Post gave a version of Gödel's Incompleteness Theorem using his creative sets, where originally Gödel had in some sense constructed a sentence that could be freely translated as saying "I am unprovable in this axiomatic theory." However, Gödel's proof did not work from the concept of true sentences, and rather used the concept of a consistent theory, which led to the Second incompleteness theorem. After Post completed his version of incompleteness he then added the following:

"The conclusion is unescapable that even for such a fixed, well defined body of mathematical propositions, mathematical thinking is, and must remain, essentially creative."[2]

The usual creative set K defined using the diagonal function d(x) has its own historical development. Alan Turing in a 1936 article on the Turing machine showed the existence of a universal computer that computes the  \Phi function. The function \Phi is defined such that  \Phi(w,x) = (the result of applying the instructions coded by w to the input x ), and is universal in the sense that any calculable partial function f is given by  f(x)= \Phi(e,x) for all  x where  e codes the instructions for f. Using the above notation  \Phi(e,x)= [[e]](x) , and the diagonal function arises quite naturally as  d(x) = [[x]](x)+1. Ultimately, these ideas are connected to Church's thesis that says the mathematical notion of computable partial functions is the correct formalization of an effectively calculable partial function, which can neither be proved or disproved. Church used Lambda calculus, Turing an idealized computer, and later Emil Post in his approach, all of which are equivalent.

Notes[edit]

  1. ^ Soare (1987); Rogers (1987).
  2. ^ a b Enderton (2010), pp. 79, 80, 120.

References[edit]