Einfache und immune Mengen

Einfache und immune Mengen sind Klassen von Teilmengen der natürlichen Zahlen und liefern wichtige Gegenbeispiele in der Berechenbarkeitstheorie. Sie sind eng mit dem Begriff der rekursiven Aufzählbarkeit (RE) verbunden: Während immune Mengen genau die abzählbar unendlichen Mengen natürlicher Zahlen sind, die keine unendliche rekursiv aufzählbare Teilmenge besitzen, sind die einfachen Mengen die rekursiv aufzählbaren Komplemente immuner Mengen. Die Definitionen lassen sich weiter verstärken und führen so auf den Begriff der hyper- oder gar hyperhypereinfachen Mengen.

Emil Post vermutete bereits in den 1940er-Jahren die Existenz einfacher Mengen, doch erst 1956 bzw. 1957 konnte dies (unabhängig voneinander) von Richard Friedberg und Albert Muchnik auch bewiesen werden.

Definition

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

Eine Menge

A\subseteq \mathbb {N}

natürlicher Zahlen heiße immun, falls gilt

\vert A\vert =\vert \mathbb {N} \vert \land \forall n\in \mathbb {N} \colon \vert W_{n}\vert =\vert \mathbb {N} \vert \Rightarrow W_{n}\nsubseteq A

.

(d. h. $A$ ist abzählbar unendlich, besitzt aber keine unendliche rekursiv aufzählbare Teilmenge). Hier bezeichne $\vert \cdot \vert$ die Kardinalität einer Menge.

Eine Menge

B\subseteq \mathbb {N}

heiße nun einfach, falls sie selbst rekursiv aufzählbar und ihr Komplement

{\overline {B}}=\mathbb {N} \setminus B

immun ist.

Geschichte

Als Post 1944 begann, Probleme nach ihrer Entscheidbarkeit zu vergleichen^[1], stellte sich schnell die Frage, ob jede rekursiv aufzählbare Menge, die nicht mehr entscheidbar ist, automatisch schon vollständig für die aufzählbaren Mengen ist. Nun besitzen Komplemente RE-vollständiger Mengen (genauer alle produktiven Mengen) eine unendliche aufzählbare Teilmenge. Das heißt, die Existenz von einfachen Mengen ist bereits hinreichend für die negative Beantwortung der obigen Frage. Post selbst vermutete diese Existenz, konnte sie allerdings noch nicht beweisen. Erst als Friedberg^[2] und Muchnik^[3] 1956/57 das (allgemeinere) Postsche Problem lösten, konstruierten sie en passant die erste einfache Menge. Dies war außerdem der erste Beweis in der Geschichte der Berechenbarkeitstheorie, der mit Hilfe der Prioritätsmethode geführt wurde. Heute sind dagegen deutlich simplere Konstruktionen einfacher Mengen bekannt.

Beispiel

Nach Voraussetzung gibt es eine Turing-Maschine $M$ (oder einen Algorithmus in einem alternativen Berechenbarkeitsmodell), die bei Eingabe $n\in \mathbb {N}$ die Menge $W_{n}\subseteq \mathbb {N}$ aufzählt. Sei nun $f\colon \mathbb {N} \rightsquigarrow \mathbb {N}$ diejenige partielle Zahlfunktion, bei der $f(n)$ stets das erste von $M$ gefundene Element $y\in W_{n}$ ist, für das $y>2n$ gilt, falls ein solches existiert. Dann ist offenbar $f\in {\mathcal {P}}$ (partiell) berechenbar und ihr Wertebereich $range(f)$ ist einfach.

Analog lassen sich so auch weitere einfache Mengen konstruieren.^[4]

Eigenschaften

Immune Mengen sind nicht rekursiv aufzählbar, andernfalls würden sie ja sich selbst als unendliche aufzählbare Teilmenge enthalten.
Eine unendliche Menge ist genau dann immun, wenn sie keine unendliche entscheidbare Teilmenge enthält.
Einfache Mengen sind daher nicht entscheidbar.
Immune Mengen sind per Konstruktion nicht produktiv und einfache Mengen daher auch nicht kreativ.
Nach dem Satz von Myhill sind einfache Mengen also nicht RE-vollständig.
Es gibt ein Paar $A;B\subseteq \mathbb {N}$ einfacher Mengen, das die natürlichen Zahlen ausschöpft $A\cup B=\mathbb {N}$ .^[5]

Hypereinfache und hyperimmune Mengen

Man sagt, eine geordnete Menge $A=\{z_{1}<z_{2}<z_{3}<\cdots \}\subseteq \mathbb {N}$ natürlicher Zahlen werde durch eine Zahlenfunktion $h\colon \mathbb {N} \to \mathbb {N}$ majorisiert, falls $\forall x\in \mathbb {N} \colon h(x)\geq z_{x}$ gilt, der Funktionswert $h(x)$ also stets mindestens so groß ist wie der $x$ -kleinste Wert von $A$ .

Eine Menge

A

heiße hyperimmun (h.i.), falls sie von keiner total berechenbaren Funktion

h\in {\mathcal {R}}

majorisiert wird.

Eine Menge

B\subseteq \mathbb {N}

heiße dann hypereinfach (h.s.; von engl. hypersimple), falls sie rekursiv aufzählbar und ihr Komplement h.i. ist.

Hypereinfache Mengen sind notwendig unendlich.
Hyperimmune Mengen sind stets immun und hypereinfache Mengen daher immer auch einfach.
Es gibt einfache Mengen, die nicht hypereinfach sind.^[6]
Der Schnitt zweier hypereinfacher Mengen ist wieder hypereinfach.
Die Vereinigung einer hyperimmunen mit einer immunen Menge ist wieder hyperimmun.

Hyperhypereinfache und hyperhyperimmune Mengen

Es gibt eine Charakterisierung von h.i. Mengen, die gelegentlich auch als alternative Definition verwendet wird:

Es sei dafür $\{D_{i}\}_{i\in \mathbb {N} }$ eine effektive Nummerierung aller endlichen Teilmengen von $\mathbb {N}$ (bspw. $D_{i}=\{x_{1};x_{2};\dots ;x_{n}\}$ für $i=2^{x_{1}}+2^{x_{2}}+\dots +2^{x_{n}}$ ).

Eine unendliche Menge

A

ist nun genau dann hyperimmun, wenn es keine total berechenbare Funktion

f\in {\mathcal {R}}

gibt, so dass

(\forall x;y\colon \ x\neq y\Rightarrow D_{f(x)}\cap D_{f(y)}=\emptyset )\land (\forall x\colon \ D_{f(x)}\cap A\neq \emptyset )

gilt.

Mit anderen Worten ist eine unendliche Menge $A$ also h.i., wenn es keine – in kanonischen Indizes – berechenbare Liste von paarweise disjunkten endlichen Mengen gibt, die alle $A$ schneiden.

Wenn man nun von den kanonischen $D$ -Indizes zu den oben eingeführten allgemeineren $W$ -Indizes übergeht, ergibt sich die Definition von hyperhyperimmunen Mengen. Es stellte sich heraus, dass diese sogar echt stärker ist.

Eine unendliche Menge

A

heiße hyperhyperimmun (h.h.i.), falls es keine total berechenbare Funktion

f\in {\mathcal {R}}

gibt, so dass für jedes

x\in \mathbb {N}

die Menge

W_{f(x)}

endlich ist und

(\forall x;y\colon \ x\neq y\Rightarrow W_{f(x)}\cap W_{f(y)}=\emptyset )\land (\forall x\colon \ W_{f(x)}\cap A\neq \emptyset )

gilt.

Eine Menge ist h.h.i. falls sie unendlich ist und es keine – in $W$ -Indizes – berechenbare Liste von paarweise disjunkten endlichen Mengen gibt, die diese Menge alle schneiden.

Eine Menge Menge

B

heiße dann hyperhypereinfach (h.h.s.), falls sie rekursiv aufzählbar und ihr Komplement h.h.i. ist.

Hyperhyperimmune Mengen sind stets hyperimmun, da sich $D$ -Indizes berechenbar in $W$ -Indizes umwandeln lassen.
Es gibt hyperimmune Mengen, die nicht hyperhyperimmun sind.

Literatur

H. Rogers Jr.: Theory of recursive functions and effective computability. 2. Auflage. MIT Press, Cambridge, MA 1987, ISBN 0-262-68052-1.
P. Odifreddi: Classical Recursion Theory. Elsevier, 1989, ISBN 0-444-87295-7.

Einzelnachweise

↑ E. Post: Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society, Ausg. 50 (1944), No. 5, S. 284–316 (online, PDF-Datei; 4,0 MB).
↑ R. Friedberg: Two recursively enumerable sets of incomparable degree of unsolvability (solution of Post's problem 1944). In: Proceedings of the National Academy of Sciences. Band 43, S. 236–238 (pnas.org [PDF]).
↑ A. Muchnik: Über die Unlösbarkeit des Problems der Reduzierbarkeit in der Theorie der Algorithmen. (russisch). In: Doklady Akademii Nauk SSSR (N.S.). Band 108, 1956, S. 194–197.
↑ Setze $S=range(g)$ mit $g\in {\mathcal {P}}$ analog zu $f$ , allerdings mit $g(n)>3n$ .
↑ Setze dazu $A=S\cup 2\mathbb {N}$ und $B=S\cup 2\mathbb {N} +1$ , mit $S$ aus dem obigen Beispiel.
↑ Nehme dazu die Menge $S$ aus dem obigen Beispiel, sie ist einfach, aber ihr Komplement wird durch $h(x)=\lceil 3/2\ x\rceil$ majorisiert.

[1] E. Post: Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society, Ausg. 50 (1944), No. 5, S. 284–316 (online, PDF-Datei; 4,0 MB).

[2] R. Friedberg: Two recursively enumerable sets of incomparable degree of unsolvability (solution of Post's problem 1944). In: Proceedings of the National Academy of Sciences. Band 43, S. 236–238 (pnas.org [PDF]).

[3] A. Muchnik: Über die Unlösbarkeit des Problems der Reduzierbarkeit in der Theorie der Algorithmen. (russisch). In: Doklady Akademii Nauk SSSR (N.S.). Band 108, 1956, S. 194–197.

[4] Setze $S=range(g)$ mit $g\in {\mathcal {P}}$ analog zu $f$ , allerdings mit $g(n)>3n$ .

[5] Setze dazu $A=S\cup 2\mathbb {N}$ und $B=S\cup 2\mathbb {N} +1$ , mit $S$ aus dem obigen Beispiel.

[6] Nehme dazu die Menge $S$ aus dem obigen Beispiel, sie ist einfach, aber ihr Komplement wird durch $h(x)=\lceil 3/2\ x\rceil$ majorisiert.

[1]

[2]

[3]

[4]

[5]

[6]