Productive set
From Wikipedia, the free encyclopedia
In computability theory productive sets and creative sets are special sets with important applications in mathematical logic.
The set of all provable sentences in an axiomatic system is a recursively enumerable set. If the system is suitably complex, like first-order arithmetic, then the set of all true sentences in the system is a productive set. This directly yields Gödel's first incompleteness theorem, as a productive set is not recursively enumerable and thus cannot be identical to the set of provable sentences. Furthermore the productive set can be used to construct a new true sentence which is not provable within the axiomatic system.
Contents |
[edit] Definition
Let 
be a numbering of the recursively enumerable subsets of 
. A set 
is called productive if there exists a computable function f so that for all 
f is called the productive function for A. A set A is called creative if A is recursively enumerable and its complement 
is productive.
[edit] Examples
- the set of true (or false) closed formulas of first-order logic is a productive set
- given a gödel numbering
, the set 
is creative 
is productive with the identity function 
as a productive function
[edit] Properties
- A set S is creative if and only if its indicator function 1S is a precomplete numbering of the set {0,1}
- A creative set is recursively enumerably but not recursive
- A productive set is not recursively enumerable
[edit] 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.
