Creative Set

A recursively enumerable set  is creative if its complement is productive. Creative sets are not recursive. The property of creativeness coincides with completeness. Namely, set  is creative iff if it is many-one complete.

Elementary arithmetic formulas are built up from 0, 1, 2, ..., , , , variables, connectives, and quantifiers. The set of all true arithmetic formulas is productive. Informally speaking, this means that no axiomatization of arithmetic can capture all true formulas and nothing else. For example, consider Peano arithmetic. Under the assumption that no false arithmetic formulas are provable in this theory, provable Peano arithmetic formulas form a creative set.

REFERENCES

Davis, M. Computability and Unsolvability. New York: Dover, 1982.Kleene, S. C. Mathematical Logic. New York: Dover, 2002.

Rogers, H. Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press, 1987.