Kreative und produktive Mengen

Kreative und produktive Mengen sind Klassen von Teilmengen der natürlichen Zahlen, die in der Berechenbarkeitstheorie und der mathematischen Logik auftreten. Sie sind eng mit dem Begriff der 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[1], erst später kam eine eigene Bezeichnung für die produktiven Mengen hinzu.[2]

Definition

Es sei ${\displaystyle \{W_{n}\}_{n\in \mathbb {N} }}$ eine effektive Nummerierung aller rekursiv aufzählbarer Mengen.

Eine Menge ${\displaystyle A\subseteq \mathbb {N} }$ natürlicher Zahlen heiße produktiv, falls es eine partielle berechenbare Funktion ${\displaystyle f\colon \mathbb {N} \rightsquigarrow \mathbb {N} }$ gibt, die folgender Eigenschaft genügt:

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

Wann immer also eine rekursiv aufzählbare Menge ganz in ${\displaystyle A}$ liegt, wird ihr Index auf ein Element von ${\displaystyle A}$ abgebildet, dass nicht mehr Teil dieser Menge ist. Insbesondere ist ${\displaystyle f}$ an dieser Stelle definiert.

In diesem Fall wird ${\displaystyle f}$ eine produktive Funktion für ${\displaystyle A}$ genannt.

Eine Menge ${\displaystyle B\subseteq \mathbb {N} }$ heiße nun kreativ, falls sie selbst rekursiv aufzählbar und ihr Komplement ${\displaystyle {\overline {B}}=\mathbb {N} \setminus B}$ produktiv ist.

Beispiele

• Das spezielle Halteproblem ${\displaystyle K=\{n|n\in W_{n}\}}$ ist der Prototyp einer kreativen Menge[1], sein Komplement ${\displaystyle {\overline {K}}}$ ist produktiv mit der Identität als produktiver Funktion.
• Die Klasse ${\displaystyle ARITH}$ aller gültigen arithmetischen Formeln – durch eine geeignete Gödelisierung als Menge natürlicher Zahlen aufgefasst – ist produktiv, dies besagt der Erste Gödelsche Unvollständigkeitssatz.
• Die Menge ${\displaystyle TOTAL=\{n|W_{n}=\mathbb {N} \}}$ der Indizes aller total berechenbaren Funktionen ist ebenfalls produktiv.

Eigenschaften

• Die produktive Funktion lässt sich stets total und injektiv wählen.
• Produktive Mengen sind nicht rekursiv aufzählbar, für jede rekursiv aufzählbare Menge ${\displaystyle W_{n}}$ bezeugt ja ${\displaystyle f(n)}$, dass ${\displaystyle W_{n}\neq A}$ 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 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 ${\displaystyle A}$ produktiv, so auch die Menge ${\displaystyle \{n|W_{n}\subseteq A\}}$.
• Seien ${\displaystyle C;D\subseteq \mathbb {N} }$ zwei Mengen mit ${\displaystyle C\preceq _{m}D}$, d. h. ${\displaystyle C}$ sei auf ${\displaystyle D}$ many-one-reduzierbar, dann gilt:
  • Ist ${\displaystyle C}$ produktiv, so auch ${\displaystyle D}$.
  • Ist ${\displaystyle D}$ kreativ, so ist ${\displaystyle C}$ genau dann kreativ, wenn ${\displaystyle {\overline {C}}}$ 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 (online, PDF-Datei; 81 kB).

Einzelnachweise

1. 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-Datei; 4,0 MB).
2. J. Dekker: Productive sets. Transaction of the American Mathematical Society, vol. 78 (1955), no. 1, pp. 129–149 (online, PDF-Datei; 2,0 MB).