TOPICS
Search

Creative Set


A recursively enumerable set A is creative if its complement is productive. Creative sets are not recursive. The property of creativeness coincides with completeness. Namely, set A 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.


See also

Gödel's First Incompleteness Theorem, Gödel Number, Gödel's Second Incompleteness Theorem, Peano Arithmetic, Recursively Enumerable Set

This entry contributed by Alex Sakharov (author's link)

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Creative Set

Cite this as:

Sakharov, Alex. "Creative Set." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/CreativeSet.html

Subject classifications