Quelltext der Seite Kreative und produktive Mengen

'''Kreative''' und '''produktive Mengen''' sind Klassen von Teilmengen der [[Natürliche Zahl|natürlichen Zahlen]], die in der [[Berechenbarkeitstheorie]] und der [[Mathematische Logik|mathematischen Logik]] auftreten.
Sie sind eng mit dem Begriff der [[Rekursive Aufzählbarkeit|rekursiven Aufzählbarkeit]] (''RE'') verbunden:
Die produktiven Mengen sind in einem gewissen Sinne die noch am besten algorithmisch beherrschbaren Mengen, die nicht mehr rekursiv aufzählbar sind.
Dagegen sind die kreativen Mengen genau die ''RE-vollständigen''  (vgl. [[Vollständigkeit (Theoretische Informatik)]]).
Die Bezeichnung ''kreative Menge'' geht auf einen Aufsatz von [[Emil Post]] aus dem Jahre 1944 zurück<ref name="Post1944">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 [https://www.ams.org/journals/bull/1944-50-05/S0002-9904-1944-08111-1/S0002-9904-1944-08111-1.pdf (online, PDF-Datei; 4,0&nbsp;MB)].</ref>, erst später kam eine eigene Bezeichnung für die ''produktiven Mengen'' hinzu.<ref>J. Dekker: ''Productive sets.'' Transaction of the American Mathematical Society, vol. 78 (1955), no. 1, pp. 129–149 [https://www.ams.org/journals/tran/1955-078-01/S0002-9947-1955-0067049-X/S0002-9947-1955-0067049-X.pdf (online, PDF-Datei; 2,0&nbsp;MB)].</ref>

== Definition ==
Es sei <math>\{W_n\}_{n \in \N}</math> eine [[Gödelnummer|effektive Nummerierung]] aller rekursiv aufzählbarer Mengen.

Eine Menge <math>A \subseteq \N</math> natürlicher Zahlen heiße ''produktiv'', falls es eine [[Partielle Funktion|partielle]] [[Berechenbarkeit|berechenbare]] Funktion <math>f \colon \N \rightsquigarrow \N</math> gibt, die folgender Eigenschaft genügt:
:<math>\forall n \in \N \colon ( W_n \subseteq A \Rightarrow f(n) \in A \setminus W_n)</math>
Wann immer also eine rekursiv aufzählbare Menge ganz in <math>A</math> liegt, wird ihr Index auf ein Element von <math>A</math> abgebildet, dass nicht mehr Teil dieser Menge ist.
Insbesondere ist <math>f</math> an dieser Stelle definiert.

In diesem Fall wird <math>f</math> eine ''produktive Funktion'' für <math>A</math> genannt.

Eine Menge <math>B \subseteq \N</math> heiße nun ''kreativ'', falls sie selbst rekursiv aufzählbar und ihr [[Komplement (Mengenlehre)|Komplement]] <math>\overline{B} = \N \setminus B</math> produktiv ist.

== Beispiele ==
* Das [[Diagonalsprache#Das Komplement von D ist semi-entscheidbar|spezielle Halteproblem]] <math>K = \{n | n \in W_n\}</math> ist der Prototyp einer kreativen Menge<ref name="Post1944"/>, sein Komplement <math>\overline{K}</math> ist produktiv mit der [[Identische Abbildung|Identität]] als produktiver Funktion.
* Die Klasse <math>ARITH</math> aller [[Gültigkeit#Logische Gültigkeit (= logische Wahrheit)|gültigen]] [[Arithmetik|arithmetischen]] Formeln – durch eine [[Gödelisierung#Gödelisierung von zahlentheoretischen Aussagen|geeignete Gödelisierung]] als Menge natürlicher Zahlen aufgefasst – ist produktiv, dies besagt der [[Gödelscher Unvollständigkeitssatz#Erster Unvollständigkeitssatz|Erste Gödelsche Unvollständigkeitssatz]].
* Die Menge <math>TOTAL = \{n | W_n = \N \}</math> der Indizes aller total berechenbaren Funktionen ist ebenfalls produktiv.

== Eigenschaften ==
* Die produktive Funktion lässt sich stets [[Partielle Funktion|total]] und [[Injektivität|injektiv]] wählen.
* Produktive Mengen sind nicht rekursiv aufzählbar, für jede rekursiv aufzählbare Menge <math>W_n</math> bezeugt ja <math>f(n)</math>, dass <math>W_n \neq A</math> gilt.
* Allerdings besitzt jede produktive Menge eine unendliche, rekursiv aufzählbare Teilmenge.
** Insbesondere sind also produktive Mengen stets unendlich.
* Kreative Mengen sind nicht [[entscheidbar]], denn dazu müsste ihr Komplement rekursiv aufzählbar sein.
* Eine Menge ist genau dann produktiv, wenn ihr Komplement ''[[Rekursiv aufzählbare Menge|RE]]-schwer'' ist – vgl. [[Schwere (Theoretische Informatik)]]. Dies ist der ''Satz von Myhill''.
** Eine Menge ist daher genau dann kreativ, wenn sie ''RE-vollständig'' ist.
* Ist eine Menge <math>A</math> produktiv, so auch die Menge <math>\{n|W_n \subseteq A\}</math>.
* Seien <math>C;D \subseteq \N</math> zwei Mengen mit <math>C \preceq_m D</math>, d.&nbsp;h. <math>C</math> sei auf <math>D</math> [[Reduktion (Theoretische Informatik)#Reduktionen in der Berechenbarkeitstheorie|many-one-reduzierbar]], dann gilt:
** Ist <math>C</math> produktiv, so auch <math>D</math>.
** Ist <math>D</math> kreativ, so ist <math>C</math> genau dann kreativ, wenn <math>\overline{C}</math> produktiv ist.

== Literatur ==
* 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: ''Vorlesung Berechenbarkeit.'' Kap. 5 § 3, Sommersemester 2010, Humboldt-Universität Berlin [https://www2.informatik.hu-berlin.de/logik/lehre/SS10/Berechenbarkeit/HU_SSL/kap5.pdf (online, PDF-Datei; 81&nbsp;kB)].

== Einzelnachweise ==
<references />

{{SORTIERUNG:Kreative Und Produktive Mengen}}
[[Kategorie:Berechenbarkeitstheorie]]
[[Kategorie:Mathematische Logik]]