Creative and productive quantities

Creative and productive sets are classes of subsets of the natural numbers that appear in computability theory and mathematical logic . They are closely related to the concept of recursive enumerability ( RE ): In a certain sense, the productive sets are the best algorithmically manageable sets that can no longer be recursively enumerated. In contrast, the creative sets are exactly the RE-complete (cf. completeness (Theoretical Computer Science) ). The term creative quantity goes back to an article by Emil Post from 1944; a separate term for productive quantities was only added later.

definition

Let it be an effective numbering of all recursively enumerable sets. ${\displaystyle \{W_{n}\}_{n\in \mathbb {N} }}$

A set of natural numbers is called productive if there is a partially computable function that satisfies the following property: ${\displaystyle A\subseteq \mathbb {N} }$ ${\displaystyle f\colon \mathbb {N} \rightsquigarrow \mathbb {N} }$

${\displaystyle \forall n\in \mathbb {N} \colon (W_{n}\subseteq A\Rightarrow f(n)\in A\setminus W_{n})}$

Whenever a recursively enumerable set is entirely in , its index is mapped to an element of that is no longer part of this set. In particular, it is defined at this point. ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle f}$

In this case, a productive function for called. ${\displaystyle f}$ ${\displaystyle A}$

A lot is now called creative if it is itself recursively enumerable and its complement is productive. ${\displaystyle B\subseteq \mathbb {N} }$ ${\displaystyle {\overline {B}}=\mathbb {N} \setminus B}$

Examples

• The special holding problem is the prototype of a creative set; its complement is productive with identity as a productive function. ${\displaystyle K=\{n|n\in W_{n}\}}$ ${\displaystyle {\overline {K}}}$
• The class of all valid arithmetic formulas - understood by a suitable Godelization as a set of natural numbers - is productive, this is what Godel's First Incompleteness Theorem says . ${\displaystyle ARITH}$
• The set of indices of all totally computable functions is also productive. ${\displaystyle TOTAL=\{n|W_{n}=\mathbb {N} \}}$

properties

• The productive function can always be selected totally and injectively .
• Productive sets are not recursively enumerable, for every recursively enumerable set testifies that it holds. ${\displaystyle W_{n}}$ ${\displaystyle f(n)}$ ${\displaystyle W_{n}\neq A}$
• However, every productive set has an infinite, recursively enumerable subset.
  • In particular, productive sets are always infinite.
• Creative sets are not decidable because their complement would have to be recursively enumerable.
• A set is productive if and only if its complement is RE heavy - cf. Difficulty (theoretical computer science) . This is Myhill's theorem .
  • A lot is therefore creative precisely when it is RE-complete .
• If a lot is productive, so is the crowd . ${\displaystyle A}$ ${\displaystyle \{n|W_{n}\subseteq A\}}$
• Let two sets with , i.e. H. be reducible to many-one , then: ${\displaystyle C;D\subseteq \mathbb {N} }$ ${\displaystyle C\preceq _{m}D}$ ${\displaystyle C}$ ${\displaystyle D}$
  • Is productive, so too . ${\displaystyle C}$ ${\displaystyle D}$
  • If you are creative, you are creative when you are productive. ${\displaystyle D}$ ${\displaystyle C}$ ${\displaystyle {\overline {C}}}$

literature

• R. Soare: Recursively enumerable sets and degrees: A study of computable functions and computably generated sets. In: Perspectives in Mathematical Logic, 1987, Springer, Berlin. ISBN 3-540-15299-7 .
• H. Rogers Jr.: Theory of recursive functions and effective computability. 2nd ed., 1987, MIT Press, Cambridge MA. ISBN 0-262-68052-1 .
• M. Grohe: Lecture predictability. Cape. 5 § 3, summer semester 2010, Humboldt University Berlin (online, PDF file; 81 kB) .

Individual evidence

1. ↑ ^{a b} E. Post: Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society, vol. 50 (1944), no.5, pp. 284–316 (online, PDF file; 4.0 MB) .
2. ^ J. Dekker: Productive sets. Transaction of the American Mathematical Society, vol. 78 (1955), no. 1, pp. 129–149 (online, PDF file; 2.0 MB) .