Productive set

From Wikipedia, the free encyclopedia

This article or section does not cite its references or sources.
Please help improve this article by introducing appropriate citations. (help, get involved!) This article has been tagged since July 2006.

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.

[edit] Definition

Let $W_{i \in \mathbb{N}}$ be a numbering of the recursively enumerable subsets of $\mathbb{N}$ . A set $A \subset \mathbb{N}$ is called productive if there exists a computable function $f$ so that for all $i \in \mathbb{N}$

$W_i \subseteq A \Rightarrow f(i) \in A \setminus W_i.$

$f$ is called the productive function for $A$ . A set A is called creative if A is recursively enumerable and its complement $\mathbb{N}\setminus A$ 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 $\varphi$ , the set $K_{\varphi}:=\{i | i \in \mathrm{Dom}(\varphi_i)\}$ is creative
$\mathbb{N} \setminus K_{\varphi}$ is productive with the identity function $\mathrm{id}_{\mathbb{N}}$ as a productive function

[edit] Properties

A set $S$ is creative if and only if its indicator function $1 S$ 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

Retrieved from "http://en.wikipedia.org../../../p/r/o/Productive_set.html"

Categories: Articles lacking sources from July 2006 | All articles lacking sources | Recursion theory